|
Authored by: Anonymous on Tuesday, May 15 2012 @ 11:06 AM EDT |
No, you fell for Oracles effort confuse. The ultimate string is not a symbol,
it is the data. "01" refers to a location in the table. If it was a
symbol, a resolution step would be needed to find the location it is referring
in the table. I think it was Terrence Parr's testimony that is the clearest on
this.[ Reply to This | Parent | # ]
|
|
Authored by: hardmath on Tuesday, May 15 2012 @ 11:07 AM EDT |
No, he was talking about a data value that, in the illustrated
case under discussion was (or could be) a string.
However this string (or symbol if you wish) is something that
will exist in the string data table at runtime, not in the
instruction stream at install time. The patent refers to
"dynamic resolution" of symbolic references in the instruction
stream. Such things do not exist in the installed Dalvik
code, nor in the pre-installation (pre-dexopt) Dalvik code.
---
"Prolog is an efficient programming language because it is a very stupid theorem
prover." -- Richard O'Keefe[ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 11:10 AM EDT |
So, it's not really that a meaningless computer-generated number can be a
symbolic reference, which is what yesterday's article made is seem like Dr.
Mitchell was claiming, and is utter nonsense. It is that such a number can be a
non-symbolic reference to a symbol--so symbolic references do exist at this
level, and are used, but are referred to indirectly by some of the
"machinery".[ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 11:37 AM EDT |
I appreciate your concern, but a number may be directly calculated as an
address by taking the base address and multiplying the number by the bytes
needed for storage of a value. While the base may be moved as memory is
freed
and allocated, that is transparent to the program. A symbol is more
abstract
and contains no information that may be used to find the address
location of
its value. If I understand the testimony and Oracle's theory correctly,
they
are saying that a numeric value which dereferences to a pointer, which is
also
a numeric value for an address calculation, is the same as deferring
address
offset specifics and placing symbols - to be dereferenced at run-time -
in the
byte code. Since pointer dereferencing pre-dates java by at least 20
years, the
obvious question is what did Sun patent? Note: I do not buy
that in this
case Oracle is going to court with one of the Ridiculous contest
winners or
that Sun didn't truly move forward the arts and sciences of writing a
virtual
machine. Based on testimony and the Groklaw reports, I believe Google
implemented their virtual machine differently than
Sun's. Given the many
former Sun people working on dalvik, one is tempted to
suggested that its
design is informed by experience and knowledge about what
happened when the
rubber hit the road and that a smartphone has to be more
efficient at runtime
because cycles spent garbage collecting or picking up the
work that had been
deferred at compilation can result in poor response to user
inputs. [ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 11:47 AM EDT |
It may involve symbolic reference but that is not what the
patent is meant to
be about. Trying to stop my eyes from
glazing over, I do not see that you have
shown that it is
dynamically resolved - from the proposed jury
instructions:
Symbolic reference: The term “symbolic
reference”
means “a reference that identifies data by a name
other than the numeric memory
location of the data, and that
is resolved dynamically rather than
statically.”
Resolve and Resolving: The term “resolving” a symbolic
reference means “at least determining the numerical memory-
location reference
that corresponds to the symbolic
reference.” [ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 12:23 PM EDT |
Well, it that code block practices the patent, there are
so many programmers that are probably infringing that it
might as well be a patent on breathing.
[ Reply to This | Parent | # ]
|
|
Authored by: tknarr on Tuesday, May 15 2012 @ 12:35 PM EDT |
I think you're confusing a symbolic reference with indirect addressing. In
indirect addressing, the instruction contains the address of a location which in
turn contains the address of the location that holds the data. Often you're
indirecting through a register, eg, "ld ax, [dx]" says "load the AX register
with the contents of the location pointed to by the DX register". But it's
equally legal on most CPUs to do something as complex as "ld ax, [0xBC80] +
0x04", which says "take the address found at location 0xBC80, add 4 bytes to it,
and load the AX register with the value found at the resulting location". 0xBC80
in this case might be the address of a pointer variable pointing to the start of
a structure., with 0x04 being the offset of a field in that structure. But
you'll notice all of this, while indirect and allowing for dynamic changes at
run-time, doesn't involve symbols at all. It's all addresses, directly or
indirectly.
A symbolic reference, OTOH, doesn't refer to an address. It'd
contain a reference not to an address but to a name of some form (possibly
numeric, that's allowed), which has to be translated into an address at run-time
to be covered by the patent. So I'd have to have something like "ld ax,
[%ED57]", meaning "look up the entry with name 0xED57 in the symbol table,
determine what address it's at, and load the AX register with the value found at
that address". Note that the instruction doesn't say where the symbol table is
(presumably this is known elsewhere), and 0xED57 isn't a direct index into the
symbol table but a name that has to be searched for (it's a number, true, but
it's still treated as an arbitrary name for something and not a direct address
of something). The key difference is that in the case of direct or indirect
addressing if I move the variable referred to to another location I have to
change the operand of the instruction, while the symbolic reference remains a
reference to %ED57 regardless of where I move the variable to in
memory.
That all of course leads to the case where you optimize away the
symbolic reference entirely: the symbol table resides at a known address and
symbol "names" are merely indexes into the symbol table. I'd argue that at that
point you've taken it outside the realm of what's covered by the patent
entirely. You've taken the symbolic reference and, in the name of performance
optimization, turned it into non-symbolic indirect addressing. And that in fact
is a common optimization, so common that symbolic linkers were doing it 30 years
ago (long before Oracle's patents were filed). A patent doesn't cover
everything. If I file a patent that covers hanging a door by measuring and
marking screw-holes for the hinges an equal distance from the edge of the door,
and then someone optimizes the process by making hinges with tabs on them so
they self-align on the doorframe and I don't need to measure and mark the
screw-holes, their new process does not infringe on my patent because
they're simply not doing what my patent describes. They get the same result, but
they're not using the method I patented to get there. [ Reply to This | Parent | # ]
|
|
Authored by: PolR on Tuesday, May 15 2012 @ 12:37 PM EDT |
I had for a while in the back of my mind this idea that it is unusual for a
bytecode to contain character stings inline, even for symbolic references. A
more normal bytecode design would use a pointer to the string which is stored
somewhere else. A pointer is a number. For the purposes of this patent, is a
pointer a symbolic reference or a numeric reference?
Based on your analysis, it seems that the contested references are indeed some
form of pointers to a complex data structure containing symbolic references. We
don't have a straightforward symbolic reference like an inline symbol or a
direct pointer to one. But if we follow the indirections and compute the offsets
some symbol will turn up. So we have an issue of semantics. For purpose of the
patent is this the kind of symbolic reference which is being claimed? Or to put
it differently, what is the invention? What are the words of the patent meant to
describe? Do they claim everything which could somehow be called a
"symbolic reference" according to some legal explanation of how the
program is written? Or do they have a specific kind of symbolic references in
mind?
There is a reason mathematicians use a mathematical notation and there is a
reason programmers use programming languages. There are concepts which cannot be
expressed clearly in plain English or even in the legalese dialect of English.
Insisting that these concepts are claimed using legalese is bound to provoke
these type of ambiguity.
The real reason Dr Mitchell testimony is appalling is his handling of the word
"dynamically resolved". Symbolic reference in the context of this
patent is an ambiguous term. It reveals a problem other than the integrity of Dr
Mitchell. It shows that the legalese language of patents is unfit to clearly
describe what are the software inventions.
[ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 12:38 PM EDT |
It is very clear here that the pointer to the symbol is
replaced with the field offset. Any sane programmer is going
to consider a pointer to a string equivalent to a literal
string in an instruction stream.
But this, by itself, has been practised by compilers since
the 60s.
I have gotten a bit lost on what claims we are dealing with
in this patent. 13 would seems to cover what dexopt is
doing, but I can't see it being valid. Most of the others
depend on this being done at the same time as evaluation of
instructions.[ Reply to This | Parent | # ]
|
|
Authored by: Christian on Tuesday, May 15 2012 @ 12:43 PM EDT |
Rereading your post and the testimony, I can't tell what exactly Mr. MacFadden
is talking about with that statement. It was made during recross and describing
an exhibit that we don't have to look at and explaining his previous testimony
which we don't have. It is not clear whether these statements taken without
context are describing the actions of the virtual machine or of dexopt.
MacFadden claimed that there one is sort of an alternate front end for the other
with the code mixed together. The difference is important, because dexopt can
resolve symbolic references without violating the patent. From the partial
testimony we have, it sounds like perhaps the code that goes into dexopt
has references of the form field@CCCC which arguably is a symbolic reference,
while the code interpreted by the vm has references of the form fieldoff@CCCC
which are not symbolic references.
We do not have enough information to
resolve this, as far as I can tell. Someone here may understand the Dalvik
internals enough to explain it. [ Reply to This | Parent | # ]
|
|
Authored by: jbb on Tuesday, May 15 2012 @ 01:00 PM EDT |
Magnificent analysis. Thanks for pursuing this so deeply. I'm actually relieved
to hear that Mitchell was telling the truth.
--- Our job is to remind
ourselves that there are more contexts
than the one we’re in now — the one that we think is reality.
-- Alan Kay [ Reply to This | Parent | # ]
|
|
Authored by: Ian Al on Tuesday, May 15 2012 @ 01:19 PM EDT |
I think the key claim in '104 is claim 11 although we know that the patent calls
for the symbolic reference resolution to be done at run-time in the run-time
environment. I understand that this is always done in the 'production' Java
machine and not in the Java development run-time
environment:
[11-preamble] 11. An apparatus
comprising:
[11-a] a memory containing intermediate form object code
constituted by a set of instructions, certain of said instructions containing
one or more symbolic references;
[11-b] and a processor configured to
execute said instructions containing one or more symbolic references by
determining a numerical reference corresponding to said symbolic reference,
storing said numerical references, and obtaining data in accordance to said
numerical references.
I don't know what's going on, here, so my
comments are supposition and conjecture. Apply your own tech knowledge. Please
also note that all of the claims have to be met in the one process. It
is not permissible to, say, associate dynamic resolution of numeric variable
names when an app runs in the run-time environment with optimising instruction
codes during installation and say all the claims are infringed.
dx
compiles class files to Dalvik executable code within the JDK. It does this, in
part, by using the table that relates the Java instruction names to the Java
bytecode implementation in the class files to create a static table that relates
the non-symbolic Dalvik instruction set to the implementation code. Dexopt can
be run in the JDK to optimise the .dex file by using the same (Java) table to
find the pointer in the static Dalvik table to the original Dalvik code and
substituting the pointer to the quick Dalvik code. Developers are prohibited
from carrying out dexopt in the production 'phone. The download and installation
program in the phone carries out the function automatically.
When a new
application is installed into the 'phone, the dexopt process has to be carried
out in the 'phone. There is software in the phone that allows apps to be
downloaded and installed. The same dexopt process is used by the installer, as
that used above, except that the 'phone-based dexopt is written in Dalvik code.
For this reason, it has to use routines in the Dalvik run-time library to
execute the code. The symbolic instruction name table is retained in the .dex
file to make this possible. [I deduce this on the assumption that the code you
reference is actually run in the 'phone. The most likely alternative is that the
'phone dexopt directly substitutes the quick code pointer in the Dalvik static
table.]
The dx and the dexopt programs both use symbolic reference
lookups to do their work. Neither use a running instance of the Dalvik VM to do
that work. Neither do they use a simulation of the Java VM to do that work. The
Java VM is required to run all Java programs in the JDK including dx and
dexopt.
As Dan Bornstein noted many months ago, the symbolic references
are all converted to index tables that relate the numeric Dalvik instructions to
the instruction implementation code. Only then are the programs executable in
the Dalvik run-time environment. The index tables are created by dx and dexopt
before the program is started up in the run-time environment and then
run.
Mitchell is right that symbolic references have to be resolved for
both dx and dexopt. He ignores that it is only done with Android to create the
static, non-symbolic referenced, Dalvik instruction look-up tables.
In
neither Java nor Dalvik are the symbolic references integrated with the VM byte
instructions. This is particularly important for the Dalvik run-time as it does
not contain any means of using symbolic references to point to implementation
code for the Dalvik instructions.
dx compiles class files to Dalvik
executable code within the JDK. It does this, in part, by using the table that
relates the Java instruction names to the Java bytecode implementation in the
class files to create a static table that relates the non-symbolic Dalvik
instruction set to the implementation code. Dexopt can be run in the JDK to
optimise the .dex file by using the same (Java) table to find the pointer in the
static Dalvik table to the original Dalvik code and substituting the pointer to
the quick Dalvik code. Developers are prohibited from carrying out dexopt in the
production 'phone. The download and installation program in the phone carries
out the function automatically. --- Regards
Ian Al
Software Patents: It's the disclosed functions in the patent, stupid! [ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 02:25 PM EDT |
does not mean that that is what it is doing from the patent point of view
AFAICS all that is doing is returning and index into the fieldTable[ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 02:29 PM EDT |
I'm sorry, but I think your conclusions are wrong. I'm surprised that you were
surprised to find symbol resolution code in dvmFindInstanceField, since Andrew
McFadden testified as to how that works.
Anyway, I just did the same thing
you did: G
o to the source for the IGET bytecode, and search for "#define
HANDLE_IGET_X", and see that it calls dvmDexGetResolvedF
ield() which just indexes into a table of pointers, and if that returns
NULL, then it calls dvmResolveIn
stField(). Its not surprising that resolution can be triggered during
bytecode execution, if it hasn't already been resolved. But the '104 patent
doesn't just cover resolving a symbol at runtime: it covers replacing the
symbolic reference IN the instruction with a numeric reference. Oracle
tried to show that dexopt replacing the iget with iget-quick would infringe
those claims, but that happens statically, not dynamically. If the Dalvik VM
resolves a symbolic reference at runtime, it will not replace ANYTHING in the
instruction. The instruction will already contain a numeric index, and it will
not be touched--after the symbol resolution, the instruction will still contain
the same numeric index.
I also believe that even when applying the court's claim
construction order, there's no symbolic reference IN the iget instruction.
It contains a numeric index. The symbolic reference is in a field table. Just
like in a Java VM, where the symbolic reference is in the class's constant
pool.
This is not just semantic word games. The patent requires the
symbolic reference to be IN the instruction. Dr. Mitchell testified under oath
that the number 01 was a symbolic reference, but that just isn't
true.
Consider this excerpt from the notes of Dr. Mitchell's
testimony:
Oracle: Do Dalvik instructions contain symbolic
references?
Dr. Mitchell: Yes.
Dr. Mitchell: What are they?
Dr.
Mitchell: The field indexes.
Oracle: But those are numbers, does it
matter?
Dr. Mitchell: Not at all, a number can be a symbolic
reference.
Oracle: What about the claim construction that says a number
can’t be a symbolic reference?
Dr. Mitchell: Nothing. A number is a
perfectly good name. Adding the dex file to the poster. It includes the
instructions, list of opcodes and operands, but not the resolve field
table.
Oracle: Is the field index in a Dalvik instruction a symbolic
reference?
Dr. Mitchell: It is, according to the court’s construction. It is
a reference and it identifies data. It is a name (01) and that name is not a
numeric memory location for the data (if it were, we wouldn’t have to resolve
it) and it is resolved dynamically rather than statically.
He
conflates different meanings of 'symbol' in order to make a materially false
statement about the iget instruction. The most charitable thing I can say about
the last part, is that he interprets the court's claim construction incorrectly.
Here is what it
says:
The term “symbolic reference” shall be construed as “a
reference that
identifies data by a name other than the numeric memory
location of the data, and that is resolved
dynamically rather than
statically.”
Field indexes are not names, but Dr. Mitchell
testifies that they are. I think it was materially false and misleading.[ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 04:17 PM EDT |
The divide and conquer analysis applied to trying to determine if Android uses
symbolic references in isolation from the context of the patent, while appealing
is wrong, and is anchored in trying to prove the argument that if Android does
not use Symbolic References it does not infringe patent 104.
Using set
theory :) divide the set of all symbolic references in a program or system into
two subsets:
- Those that infringe patent 104
- Those that do not
infringe patent 104
For the purpose of the court case we are
concerned with Symbolic References Type 1. There is no limitation on using
symbolic references that do not infringe the patent.
Patent 104 is a
steaming pile, particularly the 41 claims. The clearest description of the
patent is presented in the summary. The relevant parts are:
-
Under the
present invention, a hybrid compiler-interpreter comprising a compiler for
"compiling" source program code, and an interpreter for interpreting the
"compiled" code, is provided to a computer system.
-
!!Everything about
symbolic reference rewriting that doesn't need repeating!!
-
As a
result, the "compiled" intermediate form object code of a program achieves
execution performance substantially similar to that of the traditional compiled
object code, and yet it has the flexibility of not having to be recompiled when
the data objects it deals with are altered like that of the traditional
translated code, since data reference resolution is performed at the first
execution of a generated instruction comprising a data
reference.
This invention describes symbolic references in a
specific context:
- The system has two parts: a compiler and an
interpreter.
- The compiler produces byte code and the interpreter
executes bytecode.
- By 3, a portion of the compiled program can be
replaced without recompiling the whole, by defn. the smallest replaceable unit
is a .class file, and the resulting program can still be executed by the
interpreter.
- In this invention, symbolic address rewriting must be
implemented in the interpreter and must be performed each time the program is
run in an interpreter in order to accomodate the changes allowed in
3.
Android consists of three parts: a compiler, an installer and
an interpreter. Furthermore, Android produces two intermediate stage byte code
products: .dex files from the compilation phase and .odex from the installation
phase. The .dex files contains symbolic references which are erased during
conversion from .dex to .odex during installation.
The android symbolic
references are not Type 1 (infringing) since they are not erased in conformance
with the invention. Specifically, the erasure happens once on each device during
installation and never during interpretation. Portions of an android program can
not be replaced without compiling the whole and presenting the complete package
to the installer. The .odex files executed by the interpreter do not have
Symbolic Reference that can be rewritten
The court construct Symbolic
Reference depends on dynamic resolution. The same trap is evident in the
arguments surrounding Dynamically Resolved Symbolic References (DRSRs) as
desribed earlier. The patent only applies to DRSR's within the context of the
invention. Again using set theory :) There are infringing DRSR's and
non-infringing DRSR's. Android is free to use non-infringing DRSR's. Again
considering summary point 3 above, DRSR are applied in the invention to allow
the replacement of portions of the program without compiling the whole. Again
This is not possible on Android.
The upshot is that Android is not prevented
from using Symbolic References or Dynamically Resolved Symbolic References, only
that it can not use them in an infringing manner. The argumentation around
trying to establish that Android does not use one or the other in order to prove
non-infringment is unnecessary and potentially lethal to Google's case.
This
is where Mitchell is wrong, by omission and unfortunately abetted by the Google
testimony. By suggesting that Android has Symbolic References it is in
infringing. This is not necessarily true, since as argued above, a further
determination of the symbolic references in the context of the patent is
required. [ Reply to This | Parent | # ]
|
|
Authored by: Anonymous on Tuesday, May 15 2012 @ 04:55 PM EDT |
Is the patent on keeping symbols in the .class file (where they are referenced
by the bytecodes in that same .class file), symbols that are resolved by a
standard Java JVM at run-time?
One can certainly see the benefit of doing that. The version of class XX that
the compiler uses when a program refers to XX.field may be different from the
version of class XX that the program eventually uses when it runs. Trying to use
offsets rather than symbols would be murder.
So, does the patent regard everything after the compile step as
"dynamic"? In the standard Java JVMs, a .class file remains unchanged
from the time it's written by the compiler until it runs, so the resolution of
all those symbols is indeed dynamic.[ Reply to This | Parent | # ]
|
|
Authored by: jwrl on Tuesday, May 15 2012 @ 11:58 PM EDT |
Looks like this is an associative array, which there is mountains of prior art.
The code is just how I'd program one.
mumps was built on them.
[ Reply to This | Parent | # ]
|
|
Authored by: Ian Al on Wednesday, May 16 2012 @ 02:33 AM EDT |
I laced my previous supposition and conjecture with quotes from claim 11. This
is claim free.
Google: Remind the jury, what is
field@CCCC?
Mr. McFadden: It's an operand in the instruction, an index
value that identifies a location in the field table.
Google: Note
"these opcodes are reasonable candidates for static linking", what is
that?
Mr. McFadden: Replacing the CCCC value with a different value
which allows you to short-circuit one of the steps you do when accessing a
field.
Google: What in Android lets you do that?
Mr.
McFadden: Don't understand.
Google: What program does this?
Mr. McFadden: Dexopt.
This is dexopt optimising opcodes by
replacing the numeric value in the index.
Google: Others
can be inferred statically when certain assumptions are made. What's
that?
Mr. McFadden: Those are things dexopt can do.
Google:
For virtual method calls, replace method index with vtable index. What's that,
replacing one index with another index?...
Mr. McFadden: Very similar
to what we saw before. Similar operation on method invocation.
Google:
For instance field get/put, replacing field index with byte offset, is that the
same as TX-735? What is that?
Mr. McFadden: Again, this is that
field@CCCC operand, replacing that value with a byte offset into an
object.
Google: Again, what's the difference between an index and an
offset?
Mr. McFadden: Almost nothing. In this case, the index is into
a table; when I say offset, it's usually a byte offset, but it's still pretty
much the same thing...
Google: A bit of code here: static linking
using dexopt. Explain what this is, starting with line 1953 (rewrite
iget/iput).
Mr. McFadden: That's the purpose of this function: rewrite
iget/iput. The note is just a reminder of how the instruction is layed out in
memory.
Google: Line 1963, what's that?
Mr. McFadden: That's
the name of the method, and the arguments it takes.
This is dexopt
providing index table shortcuts for method calls. iget/iput seems to be the
programming that resolves the method label and puts the pointer in the index
table. This is still static optimisation by dexopt, but it is optimising the
method calls and those calls have to have their text labels.
And
finally:Oracle: Do Dalvik instructions contain symbolic
references?
Dr. Mitchell: Yes.
Dr. Mitchell: What are
they?
Dr. Mitchell: The field indexes.
Oracle: But those are
numbers, does it matter?
Dr. Mitchell: Not at all, a number can be a
symbolic reference.
Dr. Mitchell did not lie. A number represented
by text character values can be a symbolic reference, e.g. "One" or "1".The
Oracle lawyer lied. He said that the field indexes were numbers and that is a
lie. As Mr. McFadden stated perfectly clearly, it is not a number, it is "an
index value ".
--- Regards
Ian Al
Software Patents: It's the disclosed functions in the patent, stupid! [ Reply to This | Parent | # ]
|
|
|
|
|