Sequentially encoded data structures that support bidirectional scanning
AssigneeHoneywell Information Systems Inc.
InventorRobert J. Lechner
Life of this patent
Estimating the term…
Abstract
A coding method and apparatus that supports bidirectional scanning is disclosed for sequences of fields of variable length and/or type. Symmetric difference separators of the two immediately adjacent data field types are generated by exclusive-OR addition and utilized as punctuation marks to support bidirectional scanning. Parity checking techniques and hardware are utilized to resolve boundary alignment problems when a separator is in error. An extension of the concept of the invention to hierarchical parenthesized structures permit skipping over subtrees without scanning their contents.
Claims21
A bidirectional scanning apparatus for determining, in a forward or reverse direction, the address of a next sequential field desired in a sequence of fields of variable length, said fields in said sequence being separated from each other by symmetric difference separators, each symmetric difference separator comprised of the carry-free exclusive-OR addition of the values of the lengths of its adjacent fields on either side of said symmetric difference separator, said bidirectional scanning apparatus comprising:
- a. first means, responsive to one of said sequential difference separators currently being scanned and to a length or type code for one adjacent field of said one of said sequential difference separators, for generating the length or type code of the other adjacent field;
- b. second means, coupled to said first means, for storing the location of the field currently being scanned;
- and,
- c. third means, coupled to said first and second means, for algebraically adding the length of either adjacent field to the location of the separator preceding the left edge of the field currently being scanned, whereby the address of the next sequential field separator desired is generated.
A bidirectional scanning apparatus for determining, in a forward or reverse direction, the address of a next sequential field desired in a sequence of fields of variable length, said fields in said sequence being separated from each other by symmetric difference separators, each symmetric difference separator comprised of the carry-free exclusive-OR sum of the lengths of its adjacent fields on either side of said symmetric difference separator, said bidirectional scanning apparatus comprising:
- a. first means, responsive to one of the symmetric difference separators currently being scanned and to an adjacent field of said one of said symmetric difference separators, for exclusive-OR adding, carry-free, said one of said symmetric difference separators to said adjacent field of said one of said symmetric difference separators;
- b. second means, coupled to said first means, for storing the address of the field currently being scanned;
- and,
- c. third means, coupled to said first and second means, for binarily adding or subtracting the length of the other adjacent field to the address of the field currently being scanned,
- whereby the address of the next sequential field desired is generated.
A bidirectional scanning apparatus for scanning in a forward or reverse direction sequential tree structured data (i.e. hierarchical data) subdivided into file, record, group and field data structures, said file data structures being stored in sequence and separated from each other by file symmetric difference separators associated with respective ones of said adjacent file data structures, said record data structures being in sequence within said file data structures and separated from each other by record symmetric difference separators associated with respective ones of said adjacent record data structures, said group data structures being in sequence within said record data structures and separated from each other by group symmetric difference separators associated with respective ones of said adjacent group data structures, and said field data structures being in sequence within said group data structures and separated from each other by field symmetric difference separators associated with respective ones of said adjacent field data structures, each symmetric difference separator comprised of the carry-free exclusive-OR addition of the lengths of its associated adjacent data structures, said bidirectional scanning apparatus for further determining the address of a next sequential data structure desired at any level, said bidirectional scanning apparatus comprising:
- a. first means, responsive to a first of said sequential difference separators currently being scanned and to the length of a first adjacent data structure associated with said first of said symmetric difference separators, for carry-free exclusive-OR addition of said first of said symmetric difference separators to said length of said first adjacent data structure;
- b. second means, coupled to said first means, for storing the address of said first symmetric difference separator associated with said first data structure;
- c. third means, coupled to said first means, for storing the signed length of a second data structure generated by said first means, and associated with said first symmetric difference separator;
- and,
- d. fourth means, coupled to said second and third means, for binarily adding the signed length of said second data structure to said address of said first symmetric difference separator,
- whereby the address of the next sequential data structure desired is generated.
Dependencies are inferred from the claim text.