A reader left a comment yesterday, with contact information, on possible prior art. Even though it's too late for this trial, it's never too late to bring prior art to the attention of the USPTO, and who knows what will happen in this case and in Oracle's moves thereafter. Plus the '104 patent has been found preliminarily invalid, but there are further steps to go, so it might be useful. And while Google isn't relying on prior art in this trial on the '104 patent or the '520, instead saying it doesn't use the technology described in the patent, what if Oracle has plans, if the jury brings in a verdict for Oracle on the patents, to go after others? Also, if the '104 patent is finally found invalid by the USPTO, any damages linked to that patent will be wiped out. So I wanted to highlight the comment, just in case it's useful.

Jump To Comments

[Update 1, Update 2, Update 3]

I'm sad to tell you that I don't think our reporter made it to the courtroom today. We're like the jury. Illnesses and unexpected events can stand in the way. And unfortunately, we don't have ten other people who have to show up anyway. So we will rely on the tweeting journalists today for any news. For now, the jurors are deliberating, after hearing a readback of the testimony by Dr. Mitchell and the judge telling the jury not to give that testimony too much weight just because they heard it most recently.

All the techies here at Groklaw wish they could tell the jury that they shouldn't give it any weight at all, because it's not correct information, from all they know. And they know plenty. They write code. If you go to read the comments on the day Mitchell gave that testimony, you'll see what I mean. But that's life. It's up to the jury to decide who to believe.

Here is the prior art comment:

Dynamic Symbolic Lookup Patent as describe By Van Nest closing comments: Prior Art 1970's
Authored by: Anonymous on Wednesday, May 16 2012 @ 06:50 PM EDT

I have prior art from the 1970's:

The macro assembler, link, and the operating system job loader in the RT-11 operating system performed resolution from symbolic names to numbers to addresses in both a static form and a dynamic form.

The static form was for programs loaded at a fixed address (0) and the dynamic was for programs loaded at arbitrary locations.

Dynamic loaded operating system components ("handlers") also had hand-coded relocation using a standard format.

This is the reason software patents should be discontinued, there is almost always prior art.

/s/ Jim Williams

[email]

Update: There is another jury question, according to Rachel King:

All of team Oracle is standing around the table read the question. There's a lot of smiling and smirking. Most of team Goog not here yet

Update 2: Uh oh. Clearly whoever wouldn't be unanimous in the first verdict didn't catch a cold or have her car break down. The jury has sent a note asking why the verdict has to be unanimous. The judge has a tricky assignment here. The law requires a unanimous verdict, but no one on a jury is supposed to go against his true decision as to what the verdict should be, even if it results in a hung jury. And the jury wants to hear Dr. Terence Parr's testimony read back, specifically about his tests. So it's a battle of the experts. Sad that no technically qualified people are on this jury. How are they supposed to know which is right, if they have simply no basis?

Here's the section from Dr. Parr's testimony that I think they are referring to, although the lawyers will be deciding how much they hear, but it's the part where he describes the testing he did and declares point blank, according to our reporter's notes, that he doesn't agree with Dr. Mitchell at all, at all, at all:

Terence Parr on the Stand, Google Asking the Questions:

Google: Dr. Parr, could you look at the '520 patent, claim 1, which Oracle is asserting in this case?

Taking a look at claim 1, explain what the steps in claim 1 do?

Mr. Parr: The first step is where it says "compiling source code containing the array with static values". That's the Java compilation process we talked about, where you take human-readable source code and compile it to Java bytecode. The second step, "receiving the class file into the preloader"... [basically reads the claim]

Google: What does the patent say about the clinit method you refer to? I might direct you to column 1 of the patent, around line 257.

Mr. Parr: The clinit method stands for "class initialization method". Its job is to initialize all the static elements in a class, including static arrays.

Google: In claim 1, what is "simulating execution of the bytecodes"?

Mr. Parr: I understand "execution" to mean running live on the JVM. Simulating execution is in the preloader -- it's like a dress rehearsal versus a live show. The goal is to simulate these bytecodes to determine the static initialization of the array.

Google: What's the core requirement for simulating execution on a stack machine?

Mr. Parr: Well, you need to manipulate the stack -- pushing, popping, etc.

Google: Is this described in the patent?

Mr. Parr: It does not say stack manipulation.

[Shows how the example code in the patent is operating on a stack]

"Object stack[] = new Object[stackSize]; // create stack for play execution" etc.

Google: Were you in court for Dr. Mitchell's testimony on infringement?

Mr. Parr: Yes.

Google: Do you agree with his testimony?

Mr. Parr: No.

Google: Why not?

Mr. Parr: Because dexopt doesn't use simulated execution for the purpose of determining static initialization of the array.

Google: How did you determine that?

Mr. Parr: Spent a long time looking at the dex source, running tests, etc.

Google: What's the purpose of the Android dex tool?

Mr. Parr: It takes the .class files emitted by the Java compiler, and translates them to .dex files.

The Java Virtual Machine and the Dalvik VM have completely different instruction sets, so a translation has to occur. Otherwise it's like a person who only speaks German giving instructions to someone who only speaks Portuguese.

Google: So how can Java programs run on Android?

Mr. Parr: That's what dex does. It translates Java bytecodes into Android bytecodes, so Android can execute them.

[Discussion about how dex uses simulated execution, as described extensively in its comments.]

Google: So you'd agree that the Simulator class does know how to simulate bytecodes?

Mr. Parr: Yes.

Google: So why doesn't it infringe the '520 patent?

Mr. Parr: That's because for the very specific purpose of identifying the static initialization of the array, it does something different -- it uses pattern matching.

Google: What does "identify static initialization of the array" mean?

Mr. Parr: It means to find the values that will be used to initialize the array.

Google: TX-46.17. What is that?

Mr. Parr: BytecodeArray.java. It appears to be from froyo. It's part of dex.

Google: You've looked at it before?

Mr. Parr: Yes.

Google: Where does it come from?

Mr. Parr: From the dex tool.

Google: What did you find that's relevant to your opinion?

Mr. Parr: What I identified was the specific part of the program, dex, that identified the static initialization of the array. It's in parseNewarray, line 887.

Actually, easiest is if you turn to line 948, there's a comment: "Try to match the array initialization idiom. For example, if the subsequent code is initializing an int array, we are expecting the following pattern repeatedly" -- and then you see the pattern we saw earlier, for how to initialize an array. It appeared to me to be a classic example of a pattern matcher.

Google: How do you know?

Mr. Parr: Well, I've been building parsers for 30 years. See line 965, it defines a variable called "punt" -- it's looking for something, if it doesn't find it, it fails. It's a classic example of pattern recognition.

Google: Is it manipulating the stack at all here?

Mr. Parr: No, I didn't see any stack manipulation.

Google: What are comments for?

Mr. Parr: They help future developers, or ourselves, understand what the developer was thinking.

Google: Did you find the comments consistent with what the code actually does?

Mr. Parr: I did.

Google: What experiments did you use to test your hypothesis that this was using pattern matching?

Mr. Parr: Well, first I did a simple test to see that there were no stack manipulations in the static array initialization. I put print statements in the stack manipulation instructions (push, pop), like an alarm, so they'd trigger if there was any stack manipulation. I didn't see any.

[Demonstrative, titled "parseNewarray does not use the stack", showing the output of running the program with his debug prints added]

...

During the normal operation of the simulated execution, we see stack manipulation. But as we enter the parseNewarray method, what I observed is the stack alarms went silent until the parseNewarray method had exited. But once we returned from parseNewarray, we again got stack manipulations.

Since there are no stack manipulations, it can't be using simulated execution to identify these initialization.

Google: What was the second experiment you performed?

Mr. Parr: Well, this one's a little trickier, but useful. If it were using pattern matching, then if the pattern of initializations were altered, the pattern would fail to match. But if it were using simulated execution, then a minor change wouldn't affect it and it would still work.

For example, if I say "I like apples" and someone else says "I *totally* like apples" [...]

[Starts drawing pictures for the jury; he's totally in lecture mode now]

Here are the initialization elements of the array. This is human- readable code that the compiler consumes and uses to generate bytecodes. Let's see what the bytecodes will look like.

[Very detailed description of exactly how to initialize an array in java bytecodes, to which most of the jury is remarkably attentive.]

So, this is the pattern I'm talking about: dup, iconst, iconst, store.

[Shows the pattern again for initializing the second array element.]

Google: So, at that point, what did you do to change the pattern?

Mr. Parr: First, I ran dexopt on this sequence, generated by the compiler. It does indeed create an instruction to initialize this array, all in one go. So the default output of the compiler is recognized by the dex tool as static initialization.

So, how can I change this sequence of instructions without modifying the end result? Remember a new array is already initialized to zero. I'm just going to add an extra instruction at the beginning to set it to zero again. This is a tweak that doesn't affect the code; if it executes, it wouldn't change the end array. However, if the dex tool is a pattern matcher, it'll fail to recognize this pattern.

I ran the dex tool on this modified bytecode stream, and the dex tool failed to generate an instruction to initialize these elements in one go.

Google: Professor Parr, could you show the slides you prepared?

Mr. Parr: [Shows slides comparing original bytecode with his modified bytecode that adds an extra redundant store of zero.]

You can see these extra instructions don't change anything, since that zero is already there.

Here are the Dalvik bytecode instructions created by the dex tool in response to the original bytecode sequence: it uses fill-array-data.

But with the modified code, there's no fill-array-data to initialize the array in one go. You see the normal conversion of Java bytecodes to Dalvik instructions (new-array, aput, etc.).

Google: If the dex tool were in fact simulating the execution of the Java bytecode, what would have resulted?

Mr. Parr: If it were simulating, it wouldn't care about the extra instruction.

Think of it this way. Imagine we want to match a pattern of any two numbers added together, like "1 + 2" or "3 + 4". A functionally equivalent instruction is "0 + 1 + 2" -- but it breaks the pattern of "any two numbers added together".

Google: So, what element of the patent is not found in what the dex tool does, in your opinion?

Mr. Parr: Well, it specifically requires simulated execution, but the dex tool does not use simulated execution for the purpose of static array initialization.

Claim 20: "Simulating execution of the code to identify the static initialization of the array".

Google: Were you present for Mr. Poor's testimony? Did you have an opinion?

Mr. Parr: Yes, I disagree with his conclusions; his tests weren't on real- world applications.

His tests were contrived examples which were not meant to be real- world examples. The impact of a patent -- you want to see how it's affecting real-world applications, because that's where the value is, I guess.

Google: Did you perform your own analysis of the potential impact of this functionality?

Mr. Parr: I analyzed about 20 real-world applications for the Android phone, to see what the impact was of generating this fill-array-data instruction. I determined how many arrays were used in the original program, how big the space was that they needed, and computed a percentage that indicated what percentage of the .dex file is consumed by these instructions.

Google: Where did you get these applications?

Mr. Parr: I got them from counsel.

[Applications are BooksPhone, GenieWidget, Gmail, GoogleBackupTransport, GoogleCalendarSyncAdapter, etc.]

[Shows slide with .dex file size, and the percentage of bytes in each file which are taken up by static arrays. It's around 0.05% on average, and zero for several.]

Google: Given that finding, what's your analysis of the impact of the accused functionality on an ordinary Android application?

Mr. Parr: From my experience and examining these applications, these are just not a problem.

Google: So, to summarize, what's your opinion on the '520 patent?

Mr. Parr: The dex tool uses pattern matching, not simulated execution, the reason being that it does not use a stack.

But it makes a difference to us. We need a volunteer for Monday.

Update 3: We now have the transcript [PDF] of the day.