Method and apparatus for identifying the existence of differences between two files

[0002] This application claims the benefit of U.S. Provisional application Ser. No. 60/090,062 entitled, “METHOD AND APPARATUS FOR IDENTIFYING THE EXISTENCE OF DIFFERENCES BETWEEN TWO FILES” filed on Jun. 19, 1998 by Bodie Kathrow and John Skelton and is hereby incorporated herein by reference in its entirety.

[0003] A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

[0004] The present invention is related to computer software and more specifically to computer software for determining the existence of differences between two personal computer files.

[0005] Computers systems store information in files. Some computer programs use files to store data used by the computer programs. For example, the Windows 95 operating system commercially available from Microsoft Corp. of Redmond, Wash. stores information used by the Windows operating system and other programs running under the Windows operating system in a file referred to as the Windows registry. The Windows registry contains values used to control the operation of the Windows operating system and other programs running under the Windows operating system. In addition to these values, the Windows registry also contains keys which identify each of the values. The Windows 95 operating system and many computer programs running under the Windows 95 operating system insert keys and values into the Windows registry so that the operating system and programs can operate properly.

[0006] Occasionally, the operating system or one or more computer programs may operate improperly. Among the many potential causes of such improper operation is a corrupt file used by the computer program. For example, if the Windows registry becomes corrupt, one or more computer programs or the Windows operating system may not operate properly. Because the Windows registry can be modified by any of a large number of programs and the operating system, and the Windows registry is subject to other conventional sources of a file corruption such as disk errors, the Windows registry can be a commonly suspected source of improper operation of the operating system or computer programs.

[0007] It may be therefore necessary to determine whether the Windows registry has been modified since the last time the operating system or program operated properly. If such modification has occurred, the improper operation may be resolved by restoring certain values of the Windows registry to contain values identical to those which it contained the last time the operating system or program operated properly.

[0008] One way of determining whether the Windows registry has been modified is to store a copy of the registry on a separate disk. If a computer program operates improperly, computer support personnel may visually compare each key and each value corresponding to each key in the Windows registry on the computer containing the operating system or program that is operating improperly with the copy of the Windows registry previously stored. If the Windows registry is different from the copy, the Windows registry may be restored from the copy to identify whether the differences are causing the improper operation of the computer program.

[0009] This way of determining whether the Windows registry has been modified is subject to several problems. Although the Windows registry file is relatively small, in a company with tens of thousands of computers each containing a Windows registry, storing a copy of all of the Windows registries used by the employees of the company can utilize significant storage resources. Additionally, such a visual comparison is time-consuming and subject to error.

[0010] Therefore, a system and method are needed which can quickly and easily determine whether a file, such as the Windows registry, is different from another file, such as a previously-stored version of the Windows registry, without requiring the resources necessary to duplicate every Windows registry and without requiring a visual comparison of the files.

[0011] A method and apparatus hashes some or all of two files to be compared, allowing comparison of the hash results to identify whether differences exist between the files (a file can be identified as changed over a period by hashing it at the start and end of the period). Files that hash to a different result may be identified as having differences, and files that hash to the same result may be identified as unlikely to have differences. To reduce the probability that two files that, although different, nevertheless hash to the same result and therefore will be identified as unlikely to have differences, a characteristic of each file, such as the size of each file, may be compared as well. If either the hash or the characteristics are different, the files are identified as having differences. Otherwise, the files are identified as unlikely to have differences. If differences exist between the two files, portions of one file may be used to restore portions of the other file.

[0012] The hashing of each of the files may be performed using a hash function that includes exclusive-oring bit values from such file with a finite-sized work area and storing the result in the work area. When all bytes of the work area have been exclusive-ored, each byte of the work area is replaced by a byte which can have a different value, using a translation table of bit values selected from several such tables. After the bytes of the work area have been replaced, the exclusive-or process continues using the replaced values in the work area and any additional values from the file until all of the values of the file have been exclusive-ored into the work area. The work area is then halved in size by exclusive-oring the upper half with the lower half, selecting a table and replacing the result of the exclusive-or of each half of the work area with the corresponding value in the table. The work area is repeatedly halved in this manner until it is four bytes in size to produce a four-byte hash result.

[0013] FIG. 1 is a block schematic diagram of a conventional computer system.

[0014] FIG. 2 is a block schematic diagram of an apparatus for determining whether a two personal computer files, such as two versions of a Windows registry file, contain differences according to one embodiment of the present invention.

[0015] FIG. 3 is a block schematic diagram of a hasher shown in FIG. 2 according to one embodiment of the present invention.

[0016] FIG. 4 is a flowchart illustrating a method of determining whether a two personal computer files, such as two versions of a Windows registry file, contain differences according to one embodiment of the present invention.

[0017] FIG. 5 is a flowchart illustrating each of two hashing steps of FIG. 4 according to one embodiment of the present invention.

[0018] FIG. 6 is a flowchart illustrating each of two hashing steps of FIG. 4 according to an alternate embodiment of the present invention.

[0019] The present invention may be implemented as computer software on a conventional computer system. Referring now to FIG. 1, a conventional computer system 150 for practicing the present invention is shown. Processor 160 retrieves and executes software instructions stored in storage 162 such as memory, which may be Random Access Memory (RAM) and may control other components to perform the present invention. Storage 162 may be used to store program instructions or data or both. Storage 164, such as a computer disk drive or other nonvolatile storage, may provide storage of data or program instructions. In one embodiment, storage 164 provides longer term storage of instructions and data, with storage 162 providing storage for data or instructions that may only be required for a shorter time than that of storage 164. Input device 166 such as a computer keyboard or mouse or both allows user input to the system 150. Output 168, such as a display or printer, allows the system to provide information such as instructions, data or other information to the user of the system 150. Storage input device 170 such as a conventional floppy disk drive or CD-ROM drive accepts via input 172 computer program products 174 such as a conventional floppy disk or CD-ROM or other nonvolatile storage media that may be used to transport computer instructions or data to the system 150. Computer program product 174 has encoded thereon computer readable program code devices 176, such as magnetic charges in the case of a floppy disk or optical encodings in the case of a CD-ROM which are encoded as program instructions, data or both to configure the computer system 150 to operate as described below.

[0020] In one embodiment, each computer system 150 is a conventional IBM-compatible Pentium II personal computer, such as an XPS D333 commercially available from Dell Computer Corporation of Round Rock, Tex. running the Windows 95 operating system commercially available from Microsoft Corporation of Redmond Wash., although other systems may be used.

[0021] Referring now to FIG. 2, an apparatus for determining whether a two personal computer files, such as two versions of a Windows registry file, contain differences is shown according to one embodiment of the present invention. The two personal computer files may coexist, or may exist at different points in time. As used herein, the two computer files may in fact be the same file, existing either at a different time or at the same time. The description below describes two versions of the same file at two different points in time, but the present invention also applies to two different files at the same or different times. Additionally, each of the two files may physically exist as a single file or divided into multiple files. The description below uses a Windows registry file as an example, however, the present invention can be applied to any file in a personal computer.

[0022] File storage 210 is any storage device such as a hard disk, and stores the Windows registry file at any point in time. Administration 250 receives at input 252 a signal to fingerprint and store the information in the Windows registry file as described in more detail below. In one embodiment, this signal is received from a timer in the operating system 260 such as the Windows operating system commercially available for Microsoft Corporation of Redmond Wash., which has been set by administration 250 via output 254 as shown by the dashed lines in the figure. In another embodiment, this signal is received from an application program or from a user using a keyboard coupled to input 252.

[0023] In one embodiment, the signal received at input 252 includes the name of the file stored in file storage 210 that contains the Windows registry. In another embodiment, the Windows registry file is always stored using the same name, and the filename is implied as this name. In response to the signal received at input 252, administration 250 signals hasher 222, characteristic identifier 224 and extractor 226, described below. This signal may contain the filename of the file to be processed.

[0024] Hasher 222 hashes some or all of the Windows registry file using a hash function to produce a hash result. In one embodiment, hasher 222 uses one of the hash functions described below to hash the entire Windows registry file, including both values and keys, one value-key pair at a time. In another embodiment, values and keys are hashed using fixed length blocks of bytes, one byte at a time. In another embodiment, only the values from the Windows registry file are hashed by hasher 222. Hasher 222 can use any hash function such as Snerfu, N-Hash, MD2, MD4, MD5, SHA, Ripe-MD, HAVAL. These hash functions are described in more detail in Schnier, “Applied Cryptography, 2d ed.” (John Wiley & Sons, Inc. 1996). In another embodiment, hasher 222 uses a different hash function, such as the hash function described in more detailed below.

[0025] Characteristic identifier 224 identifies one or more characteristics of the file such as a four-byte long number of bytes of the file stored in file storage 210, the size of a fixed length block of bytes used to hash the file as described below, or the size of the “portion of interest” of such file. The portion of interest is the number of bytes hashed by hasher 222. In one embodiment, the portion of interest is the number of bytes of values in the file. In another embodiment, the portion of interest is the number of values and keys in the file. In one embodiment, characteristic identifier 224 identifies this size by requesting the size of the file from operating system 260. In another embodiment, characteristic identifier 224 requests the file stored in file storage 210 from operating system 260, reads the file, and counts the number of bytes in the file. In still another embodiment, characteristic identifier is a part of the hasher 222, and characteristic identifier counts the number of bytes hashed by hasher 222.

[0026] In an alternative embodiment of the present invention, characteristic identifier 224 identifies one or more other characteristics of the file either in place of the size or in addition to the size. Such characteristics can include the location of the file on the disk, last modification or update date of the file, or any other characteristic of the file.

[0027] Extractor 226 extracts the values, the records containing the keys and values, or fixed length blocks from the Windows registry file stored in file storage 210. In the description that follows, extractor 226 is described as extracting only values, although these other portions or any other type of portion may be extracted by extractor 226.

[0028] In one embodiment, extractor 226 requests the file from operating system 260, extracts the values and discards the keys. In another embodiment, the keys are retained. In one embodiment, the extraction is performed one value at a time, and in other embodiments, other sized portions of the file may be used to extract the file a portion at a time instead of one value at a time.

[0029] In one embodiment, hasher 222, characteristic identifier 224, and extractor 226 provide to fingerprint and content storage 230 the hash of the Windows registry file, the size of the Windows registry file, and the values or values and keys extracted from the Windows registry file, respectively. The hash and size are each four-byte values which together are referred to as the “fingerprint” of the file. Fingerprint and content storage 230 stores the fingerprint of the file, and associates this fingerprint with the values or values and keys extracted from the file. In one embodiment, fingerprint and content storage 230 stores the fingerprint and values/keys of the file in storage1232. As used herein “values/keys” and “keys/values” means either values or values and keys. The filename of the file from which the fingerprint was generated may also be stored in storage1232.

[0030] In one embodiment, the apparatus of the present invention operates as described above one time on a single known good version of the Windows registry file. In another embodiment, the apparatus of the present invention periodically operates as described above and stores in storage1232 of fingerprint and content storage 230 the fingerprint and values/keys for the Windows registry file at the end of each period. Thus, fingerprint and content storage 230 maintains two or more sets of fingerprints and values. In one embodiment, fingerprint and content storage 230 requests from operating system 260 (via a connection not shown to avoid cluttering the drawing) the date and time at which the fingerprint in values for the Windows registry file are stored in fingerprint and content storage 230. Fingerprint and content storage 230 time stamps each set of fingerprints and values/keys it receives by storing with the set this date and time.

[0031] In the event that the Windows registry file is to be compared with a prior version of the Windows registry file, administration 250 receives via input 252 a signal, optionally including a filename, indicating that the Windows registry file is to be compared. Administration 250 signals hasher 222, characteristic identifier 224, and extractor 226. Hasher 222, characteristic identifier 224, and extractor 226 repeat the operation described above on the current version of the Windows registry file stored in file storage 210. In one embodiment, the current version of the Windows registry file is always stored using the same filename, and hasher 222, file size identifier 224, and extractor 226 maintain the name of the Windows registry file to use in requesting operating system 260 to retrieve the file. In another embodiment, administration 250 provides the filename of the file on which the hasher 222, file size identifier 224, and extractor 226 will operate. Administration 250 also signals fingerprint and content storage 230, which stores the fingerprint in values in storage2234.

[0032] If fingerprint and content storage 230 stores several copies of the fingerprints and values/keys for the Windows registry file, date and time stamped as described above, fingerprint and content storage 230 provides each of the date and time stamps for each of the fingerprint and values stored in fingerprint and content storage 230 to administration 250. Administration 250 provides these dates and times at output 254 coupled to a display such as a conventional computer monitor. The user may select one of these sets of fingerprint and values/keys via input 252 coupled to an input device such as a conventional keyboard and mouse. Administration 250 provides an indication of the selected fingerprint and values set to fingerprint and content storage 230. Fingerprint and content storage 230 provides to fingerprint compare 242 the indicated set of fingerprint and values/keys for use in the comparison described below.

[0033] Administration 250 signals fingerprint compare 242. Fingerprint compare 242 requests from fingerprint and content storage 230 the fingerprint stored in storage2234, and the fingerprint from the set of fingerprint and values identified by the user as described above stored in storage1232. If only one set of fingerprint and values/keys is stored in storage1232, this fingerprint is provided along with the fingerprint in storage2234.

[0034] Fingerprint compare 242 compares the pair of fingerprints received from fingerprint and content storage 230. If the fingerprints are identical, there is a high probability that the Windows registry files corresponding to each of the pair of fingerprints received by fingerprint compare 242 are identical. If either the hash result or the characteristic of one fingerprint is different from that of the other fingerprint, the files corresponding to these fingerprints are not identical. Fingerprint compare 242 signals administration 250, which signals the user at output 254 coupled to the output device such as a conventional monitor with the result of the comparison.

[0035] If the fingerprints received by fingerprint compare 242 are not identical, fingerprint compare 242 provides the comparison result to administration 250, which displays the result to the user via output 254 and indicates that the two Windows registry files compared are not identical. In one embodiment, administration 250 signals restorer 244, and restorer 244 retrieves the values/keys corresponding to the older fingerprint of the pair received by fingerprint compare 242. In one embodiment, restorer 244 provides the values/keys to administration 250 for display to the user via output 254. The user can use the values to identify problems with the Windows registry file by performing a visual comparison of the values provided at output 254 to the values of the current version of the Windows registry file obtained via operating system 260. In one embodiment, the conventional Windows 95 “Regedit” program may be run to view the values of the current version of the Windows registry file.

[0036] In another embodiment of the present invention, restorer 244 retrieves the Windows registry file from file storage 210 via operating system 260 and identifies values which may have be different by comparing the values in the current Windows registry file from the values received via fingerprint and the values storage 230. This process is made easier in the embodiment in which the key and value pairs are extracted by extractor 226 and stored in fingerprint and content storage 230 because it is easier to match each key from storage1232 with its counterpart in storage2234 than using only the values alone. Restorer 244 prompts the user via administration 250 and output 254 with the suspected different values. The user may use input 252 to communicate the desired substitute value to restorer 244 via administration 250. Restorer 244 substitutes the substitute value so received for the value in the Windows registry file. When restorer 244 completes this process for the entire Windows registry file, restorer 244 stores the Windows registry file with the substituted values into file storage 210 via operating system 260. In one embodiment, the fingerprint and comparison described above may be performed on the new version of the Windows registry file to identify whether any differences remain between the new registry file and the file corresponding to the earlier registry file used in the prior comparison.

[0037] Referring now to FIG. 3, the hasher 222 shown in FIG. 2 is shown in more detail according to one embodiment of the present invention. File storage 310 receives the file at input 308 and operation director 330 receives the signal provided by administration 250 of FIG. 2 as described above. In one embodiment, file storage 310 is file storage 210 and operating system 260 of FIG. 2.

[0038] Operation director 330 signals portion locator 320 in response to the signal received at input 332. Portion locator 320 locates the first portion to be hashed in the file stored in file storage 310. In one embodiment, a portion to be hashed is a key-value pair. In another embodiment, a portion to be hashed is a fixed length block from the file. In another embodiment, a portion to be hashed is a record. The description that follows describes a portion to be hashed as a record, but these other types of portions or any other type of portion may be substituted.

[0039] In one embodiment, each record in the file stored in file storage 310 corresponds to one of the values of the Windows registry file. In one embodiment, portion locator 320 locates the records in the order in which they are stored in the file. Portion locator 320 passes the record to space stripper 322, which strips any leading spaces from the record. In one embodiment, space stripper 322 strips leading spaces by reducing the size of the record to omit leading spaces. In one embodiment, space stripper 322 identifies both ASCII and EBCDIC spaces, and strips either one from the record.

[0040] Space stripper 322 passes the record it receives from portion locator 320 with the leading spaces removed to length identifier 324. Length identifier 324 identifies the length of the record with the spaces stripped using a two-byte length for all records. In one embodiment, length identifier 324 increases the length it identifies by 2 and appends the two-byte length as the two most significant bytes of the record, and passes the resulting record with leading spaces stripped appended to the two-byte length of such record to exclusive-or operator 344. It isn't necessary to physically append the two-byte length to the record (thereby increasing the number of bytes in the record by 2). However, doing so simplifies the operation and description of the hasher 222. In an alternate embodiment, the length remains separate from the record but is treated in the same way as described below.

[0041] Exclusive-or operator 344 exclusive-ors each byte of the record received from length identifier 324 with one or more bytes contained in a working area storage 342 as described below. To “exclusive-or” a byte, each of the bits in a byte of the record are combined with corresponding bits in a byte of the working area storage using an exclusive-or function to produce a result. The result for each bit combination is zero if the bit in the byte of the working area storage is equal to the corresponding bit in the byte of the record and the result is one if these bits are not equal. The working area storage 342 is initialized to all ‘0’ by operation director 330 in response to the signal received at input 332.

[0042] Working area storage 342 is a 1021-byte addressable storage area. Exclusive-or operator 344 maintains two placeholders 346, 348. Placeholder 346 maintains a number corresponding to the current byte of working area storage 342. Placeholder 348 maintains the current byte of the record received from length identifier 324. Each placeholder 346,348 is initialized to zero by exclusive-or operator 344 upon a signal from the operation director 330 following receipt of the signal at input 332.

[0043] Exclusive-or operator 344 exclusive-ors the byte in working area storage corresponding to place holder 346 with the byte corresponding to place holder 348 of the record received from length identifier 324. Following this exclusive-or operation, exclusive-or operator 344 increments each of the place holders 346,348. Exclusive-or operator 344 repeats the exclusive-or operation on each byte of the record received from length identifier 324 in the above manner until place holder 348 is equal to the length of the record received from length identifier 324 or until place holder 346 is equal to 1020.

[0044] If place holder 348 is equal to the length received from length identifier 324, another record is to be processed as described above. Before the next record is processed, exclusive-or operator sets place holder 348 equal to zero and signals operation director 330. Operation director 330 signals portion locator 320 to retrieve the next record in file storage 310. If another record exists in the file stored in file storage 310, portion locator 320 retrieves it as described above. The operation of space stripper 322, length identifier 324, and exclusive-or operator 344 is repeated as described above on the new record located by portion locator 320. Note that if place holder 348 is equal to the length received from length identifier 324 and place holder 346 is equal to 1020, the operation of the apparatus described in the following paragraph is performed before the operation of the apparatus as described in this paragraph.

[0045] If place holder 346 is equal to 1020, the contents of the working area storage 342 are translated as described below, and processing continues as described above. Exclusive-or operator signals translator 340. Translator 340 requests from table identifier 352 an identifier of a table stored in table storage 354. Translator 340 translates the working area storage 342 using the table in table storage 354 identified by table identifier 352 described in more detail below. Translator 340 translates the working area storage 342 using the following process: for each byte in working area storage 342, translator 340 uses the working area storage byte as an index to a byte in the table of table storage 354 identified by table identifier 352. In one embodiment, table storage 354 contains the seven tables shown in Exhibit A attached hereto. Translator 348 retrieves this byte from the table and stores it in place of the byte in working area storage 342. When translator 340 translates every byte in working area storage 342, translator 340 signals exclusive-or operator 344 to resume operation as described herein. The current record will continue to be exclusive-ored into the working area storage, or another record will be retrieved as described above.

[0046] Each time table identifier 352 is requested to identify a table, table identifier 352 selects a different table from the table selected previously and provides the identifier of the selected table to translator 340. In one embodiment, table identifier 352 selects each table by selecting the next table identifier from an ordered set of table identifiers corresponding to all the tables in table storage 354 until all of the identifiers in the set have been selected. If additional table identifiers are requested, table identifier 352 then permutes the order of the identifiers in the set for subsequent requests for a table identifier. Thus, table identifier 352 identifies from the set of the seven table identifiers T0 through T6 one at a time in this order: T0, T1, T2, T3, T4, T5, T6. After the first set of seven table identifiers have been provided by table identifier 352 one at a time, table identifier rearranges the order of the table identifiers it provides, for example T1, T0, T2, T3, T4, T5, T6. After it provides the last identifier in the set, table identifier 352 rearranges the order of the table identifiers so that each ordered full set of seven table identifiers has an order different from the prior ordered full sets of seven table identifiers until all possible permutations of the orders of the seven tables have been used. If additional table identifiers are requested after all possible permutations of the table identifiers have been used, then table identifier 352 repeats the operation described above beginning with the order: T0, T1, T2, T3, T4, T5, T6.

[0047] When portion locator 320 is requested to locate an additional record as described above, but no additional records exist in the file stored in file storage 310, portion locator 320 signals operation director 330. In one embodiment, operation director 330 signals translator 340 to translate the working area storage 342 as described above one additional time, and in another embodiment, this additional translation is not performed. In response to the signal from portion locator 320, operation director 330 also initializes two storage areas N 334 and WA 336. N is initialized to a value ‘6’, and WA is initialized to a value ‘1018’. Operation director 330 provides the number stored in WA 336 to translator 340.

[0048] Translator 340 translates, as described herein, the upper half of the portion of working area storage 342 identified by WA 336. The portion includes bytes 0 to WA-1 of the working area storage 342. Therefore, the upper half of working area storage when WA 336 has a value of 1018 are bytes 509-1017. Before translator 340 translates the upper half of the portion of the working area storage 342, translator 340 requests an identifier of the table from table identifier 352. Translator 340 uses the table identified by table identifier 352 and stored in table storage 354 to translate the upper half of the portion of working area storage identified by operation director 330. Translator 340 signals operation director 330 that it has completed the translation process.

[0049] Operation director 330 next signals exclusive-or operator 344 by providing the contents of WA 336. Exclusive-or operator 344 exclusive-ors the upper half of the portion of the working area storage 342 identified using the contents of WA 336 with the lower half of the working area storage 342 identified using the contents of WA 336. The result is stored in the lower half of the working area storage 342. Exclusive-or operator 344 signals operation director 330 that the exclusive-or operation has completed. Operation director 330 decrements N 334 and divides WA 336 by two and stores the result of the division into WA 336 in place of the number that was there before. Operation director 330 next signals translator 340 then exclusive-or operator 344 to repeat the procedure described above. Operation director 330 continues to decrement N 334 and divide WA 336 by two and re-signal translator 340 and exclusive-or operator 344 using these new values of N 334 and WA 336 until N equals zero. This procedure results in a hash of the file stored in file storage 310 into four bytes.

[0050] Operation director 330 next signals working area storage 342 which provides the four byte result stored in the lower four bytes of working area storage 342 at output 343 to be used as four bytes of the fingerprint described above. The four-byte size of the portion of the file hashed completes the other four bytes of the eight-byte fingerprint in one embodiment, although other number of bytes may be used for the hash result and the size or other characteristic.

[0051] Referring now to FIGS. 2 and 3, in one embodiment, the fingerprint is produced in a different manner by hasher 222. Instead of hasher 222 hashing the entire file at once, hasher 222 hashes individual fixed length blocks of the file stored in file storage 210. Hasher hashes each block one at a time. Portion locator 320 locates each block sequentially in the file and hasher 222 hashes the block as described above. However, after each block is hashed, the hash result is output via output 343 and working area storage 342 is reset. This allows each block to be hashed independently of the other blocks because working area storage 342 is reset after each block is hashed.

[0052] Fingerprint and content storage 230 assembles the hash results from each block into an ordered set of hash results. Fingerprint and content storage 230 appends to the ordered set of hash results the length or other characteristic of the file received from characteristic identifier 224 in order to create the fingerprint, used as described herein. In one embodiment, a fingerprint created in this manner is referred to as a “signature”. Signatures may be created for different versions of a file or for different files like the fingerprints described above. Each signature fingerprint may be stored with an identifier of the file from which the signature was created. Extractor 226 extracts fixed length blocks from the file and stores the blocks into fingerprint and content storage 230 associated with the signature of the file.

[0053] In one embodiment, the signature containing the appended hash results of each block of the file and the characteristic is itself hashed as described above, and the hashed signature is stored along with the signature for use in comparing one signature to another.

[0054] Fingerprint compare 242 requests from fingerprint and content storage 230 the pair of signatures (and optionally the hash of each signature) corresponding to the two files of interest as described above (for example, having the same one or two different filenames received at input 252 by administration 250 and communicated to fingerprint compare 242). Fingerprint compare 242 compares the two signatures (or the hash of each signature) as described above.

[0055] When fingerprint compare 242 compares the signatures or hash of the signatures of two files, if the signatures are different, fingerprint compare 242 can investigate further to identify the specific blocks that are different between the two files being compared.

[0056] Fingerprint compare 242 compares each four-byte hash result received from storage2234 with the corresponding hash result in the signature of the known-good file that was stored in storage1232. If the hash results are the same, there is a high probability that the blocks from which the hash results were generated are identical. If the hash results are not the same, the blocks from which the hash results were generated are different. In this embodiment, fingerprint compare 242 compares each hash result, identifies hash results that are different and passes to restorer 244 a set of identifiers of the hash results it identifies as different. In one embodiment, the identifier is ‘0’ for the first hash result, ‘1’ for the second, and so on. If the original fixed length blocks are accessible using a block number, restorer 244 uses each number in the list as a block index to copy the block from the known good file if the known good file is stored unchanged in file storage 210 or from the blocks stored in fingerprint and content storage 230 otherwise, in place of the corresponding block in the other file in file storage 212 via operating system 260. If the original fixed length blocks are accessible using a byte number, restorer 244 multiplies each number in the list by the size in bytes of the fixed length blocks that were used to generate the hash result to produce one product for each number in the list. Each product is used as a byte index to the first byte in a block to be copied from the known good file to the other file. Restorer 244 restores from the known good file to the other file each block in the list in this manner.

[0057] Referring now to FIG. 4, a method for determining whether a Windows registry file has changed from a prior version is shown according to one embodiment of the present invention. A file identifier such as the name of the Windows registry file is optionally received 410. A hash result is produced from some or all of the file 412. The hash result may be generated from the entire Windows registry file, or from only the values of the Windows registry file. The hash result may be generated using a conventional hash functions such as Snerfu, N-Hash, MD2, MD4, MD5, SHA, Ripe-MD, HAVAL, or any other hash function such as the one described in more detailed herein.

[0058] One or more characteristics such as the size of some or all of the file hashed in step 412 is identified 414. In one embodiment, the size of the entire file is identified, and in another embodiment the size of the portion of the file used to generate the hash result in step 412 is identified in step 414. A fingerprint may be generated by appending 416 to the hash result generated in step 412 with the one or more characteristics identified in step 414, however, it is not necessary that the characteristic and hash result actually be appended. Key/value pairs may optionally be extracted from the Windows registry file 418 and stored along with the fingerprint of the file 420. The fingerprint and key/value pairs stored in step 420 may be archived for a later use in step 432 as described below. In one embodiment, step 420 may also include retrieving the date, time or both and storing the date, time or both with the fingerprint and key/values.

[0059] If corruption of the Windows registry file is not suspected 422, in one embodiment represented by the dashed line to the left of step 422, the method waits until corruption is suspected. In another embodiment of the present invention, steps 410 through 420 may be repeated several times after a suitable delay 408 such as one week between each repetition, so that several fingerprints and key/value pairs of the Windows registry are produced and stored.

[0060] If corruption of the Windows registry is suspected, in one embodiment the name or other identifier of the Windows registry is prompted to a user and received 424. If multiple sets of a fingerprint and key/value pairs were stored through several iterations of step 420 as described above, the specific set of the fingerprint and the key/value pairs is prompted and received as described above as a part of step 424.

[0061] A hash result is generated 426 for the current version of the Windows registry file using the same or similar hash technique as was used in step 412. One or more characteristics such as the size of a portion or all of the current version of the Windows registry is identified 428 using one of the techniques described above with reference to step 414. The characteristic identified in step 428 is optionally appended to the hash result from step 426 to generate fingerprint 430. The fingerprint produced in step 430 is compared 432 with the fingerprint stored in step 420 as identified by the user in step 424, if applicable. If the fingerprints are identical 434, the method terminates 440. In one embodiment, step 440 also includes notifying the user whether the fingerprints were identical. If the fingerprints are not identical 434, differences may be identified 436 between the values corresponding to the two fingerprints compared in step 432.

[0062] In one embodiment, step 436 comprises displaying the values and keys from the present version of the Windows registry file and displaying the values corresponding to fingerprint of step 420 compared in step 432, and allowing a user to identify differences manually. In another embodiment, differences are identified between such values and the Windows registry file using conventional comparison techniques.

[0063] Changes to the Windows registry file may optionally be received and stored into the Windows registry file 438. In one embodiment, those changes are received via input from the user. In another embodiment, the changes are portions of the values corresponding to the fingerprint stored in step 420 and used in the comparison of step 432, extracted in order to minimize the differences between such values and values of the Windows registry file.

[0064] In one embodiment, following step 438, the method terminates 440. In another embodiment represented by the dashed line below and to the right of step 438, the method repeats beginning with step 426. This repetition verifies that any changes made in step 438 have caused the current version of the Windows registry file to match the version corresponding to the fingerprint and key/value pairs stored in step 420 and optionally designated by the user in step 424.

[0065] Referring now to FIG. 5, a method of generating a hash result as described in steps 412 and 426 of FIG. 4 is shown according to one embodiment of the present invention. A table identifier is initialized to ‘zero’, a work area pointer is initialized to ‘zero’ and a work area containing 1021 bytes is initialized to ‘zero’ 510. A file record pointer is initialized to point to the first record in the file 510.

[0066] The file record pointed to by the file record pointer initialized in step 510 is retrieved from a file, and the file record pointer is incremented 512. Leading spaces are stripped 514 from the file record retrieved in step 512. In one embodiment, leading spaces are stripped from both ASCII file records as well as EBCDIC file records as described above. The length of the record stripped of its spaces is computed 514. In one embodiment, the length is computed as a two-byte length, and incremented twice, and this length is appended 514 to the record as the most significant two bytes.

[0067] As described above, incrementing and appending the length to the record is not necessary, but because it simplifies the description of the invention, such appending is used herein. In another embodiment, the length may be kept separate from the record, with the appropriate adjustments to the remainder of the method described below. In such embodiment, the length is not incremented twice, so as to represent the length of the record without an appended length.

[0068] If the length appended to the front of the record is greater than two 516, the record retrieved in step 512 contains characters other then spaces, and the method continues at step 518. If the length of the record appended in step 514 is equal to two 516, the record contains no data other than the two byte length, and the method continues at step 544, described below.

[0069] A record position variable is initialized to zero 518. The record position is a place holder to a current byte in the record as adjusted in step 514. The bits in the byte of the record pointed to by the record position are exclusive-ored with the bits in the byte of the work area pointed to by the work area pointer 520 as described above. If the work area pointer is equal to a value of 1020, the work area is translated using the table pointed to by the table identifier 530, and the next table is selected as the table identifier 532. The translation step 530 is performed by substituting each byte in the work area with the corresponding byte of the selected table identified by TableID, such translation being described in more detail above. The next table is selected in step 532 using the permutation technique described in more detail above and an identifier of the table is stored into the TableID. The method continues at step 540. If the work area pointer is not equal to 1020, the method also continues at step 540.

[0070] If the record position is equal to the length of the record 540, all bytes of the record have been processed, and the method continues at step 544. If the record position is not equal to the length of the record, the record position and work area pointer are each incremented 542, and the method continues at step 520.

[0071] When the method continues at step 544, either from steps 516 or 540 described above, if more records exist in the file 544, the record position is re-initialized to zero and the work area pointer is incremented 546. The method continues at step 512. If no more records exist in the file 544, a counter is initialized to a value of six, and a work area size variable is initialized to 1018 560. The upper half of the work area bounded by byte zero and the byte indicated by the work area size is translated as described above. The result of the translation is exclusive-ored 562 with the lower half of the work area not translated with the result being stored in the lower half of the work area. The work area size variable is divided in half, and the counter is decremented by one 566. Another table is optionally selected 568. If the counter is not equal to zero 570, steps 562 through 570 are repeated until the counter reaches zero 570. The result of the method shown in FIG. 5 is to hash the file records down to four bytes. These four bytes are provided at step 572 as the hash result, and the method terminates 574.

[0072] If the fingerprint is a signature, a slightly different embodiment of the method of the present invention is used. Referring now to FIG. 6, a method of generating a hash result as described in steps 412 and 426 of FIG. 4 is shown according to one embodiment of the present invention. The hash result generated in steps 412 and 426 is a series of hash results generated as shown in FIG. 6 and described below.

[0073] The steps of FIG. 6 operate as described with respect to FIG. 5, with the following exceptions. Each record corresponds to a fixed-length block of values or values and keys. If the record position is equal to the length 540 of the record, the method continues at step 560. If there are no more records 544, the hash result created from the last iteration of step 573 is provided 575. Step 573 replaces step 572 of FIG. 5 and involves appending the hash result from the last iteration of step 566, e.g. by storing it in addition, to any prior hash results. If no prior hash result exists, it is stored. Step 544 follows step 573. Step 547 operates as step 546 of FIG. 5, except the work area pointer does not need to be incremented as in step 546. Step 510 follows step 547. As described above, a hash of all of the hash results may be made and provided in addition to the individual hash results provided as part of step 575.

[0074] The effect is to create a hash result for each fixed length block using the technique described above for FIG. 5 hashing each fixed length block separately with an optional hash of the hash results. The signature fingerprint is then made up of the ordered collection of hash results for each fixed length block as well as the characteristic or characteristics and an optional hash of the ordered collection of hash results. Instead of the values or values and keys being stored as part of step 420, fixed length blocks are stored in addition to the fingerprint.

[0075] The use of signatures operates similarly to that of other types of fingerprints described above with respect to FIG. 4, with the following differences. Blocks may be stored from the known good file in place of values/keys as part of step 420. The signatures may be compared as described in step 434 of FIG. 4, either with each fingerprint treated as a unit, or by comparing the individual hash results that make up the signature. If the signatures are compared as a unit, the hash of the hash results may be used to compare the signatures in step 432. If differences exist, corresponding individual hash results from each signature are compared to identify differences in step 436. The blocks stored in step 420 that correspond to the individual hash results identified in step 436 may be received from the known good file or from the blocks optionally stored in step 420 and stored in the other file or file version as part of step 438 to match the other file or version with the known good file or version.

[0076] 0×00,0×02,0×01,0×03,0×04,0×06,0×05,0×07, 0×08,0×0A,0×09,0×0B,0×0C,0×0E,0×0D,0×0F, 0×10,0×12,0×11,0×13,0×14,0×16,0×15,0×17, 0×18,0×1A,0×19,0×1B,0×1C,0×1E,0×1D,0×1F, 0×20,0×22,0×21,0×23,0×24,0×26,0×25,0×27, 0×28,0×2A,0×29,0×2B,0×2C,0×2E,0×2D,0×2F, 0×30,0×32,0×31,0×33,0×34,0×36,0×35,0×37, 0×38,0×3A,0×39,0×3B,0×3C,0×3E,0×3D,0×3F, 0×40,0×42,0×41,0×43,0×44,0×46,0×45,0×47, 0×48,0×4A,0×49,0×4B,0×4C,0×4E,0×4D,0×4F, 0×50,0×52,0×51,0×53,0×54,0×56,0×55,0×57, 0×58,0×5A,0×59,0×5B,0×5C,0×5E,0×5D,0×5F, 0×60,0×62,0×61,0×63,0×64,0×66,0×65,0×67, 0×68,0×6A,0×69,0×6B,0×6C,0×6E,0×6D,0×6F, 0×70, 0×72, 0×71, 0×73,0×74,0×76, 0×75,0×77, 0×78,0×7A,0×79,0×7B,0×7C,0×7E,0×7D,0×7F, 0×80,0×82,0×81,0×83,0×84,0×86,0×85,0×87, 0×88,0×8A,0×89,0×8B,0×8C,0×8E,0×8D,0×8F, 0×90,0×92,0×91,0×93,0×94,0×96,0×95,0×97, 0×98,0×9A,0×99,0×9B,0×9C,0×9E,0×9D,0×9F, 0×A0,0×A2,0×A1,0×A3,0×A4,0×A6,0×A5,0×A7, 0×A8,0×AA,0×A9,0×AB,0×AC,0×AE,0×AD,0×AF, 0×B0,0×B2,0×B1,0×B3,0×B4,0×B6,0×B5,0×B7, 0×B8,0×BA,0×B9,0×BB,0×BC,0×BE,0×BD,0×BF, 0×C0,0×C2,0×C1,0×C3,0×C4,0×C6,0×C5,0×C7, 0×C8,0×CA,0×C9,0×CB,0×CC,0×CE,0×CD,0×CF, 0×D0,0×D2,0×D1,0×D3,0×D4,0×D6,0×D5,0×D7, 0×D8,0×DA,0×D9,0×DB,0×DC,0×DE,0×DD,0×DF, 0×E0,0×E2,0×E1,0×E3,0×E4,0×E6,0×E5,0×E7, 0×E8,0×EA,0×E9,0×EB,0×EC,0×EE,0×ED,0×EF, 0×F0,0×F2,0×F1,0×F3,0×F4,0×F6,0×F5,0×F7, 0×F8,0×FA,0×F9,0×FB,0×FC,0×FE,0×FD,0×FF,

[0077] 0×00, 0×04, 0×02, 0×06,0×01, 0×05, 0×03, 0×07, 0×08,0×0C,0×0A,0×0E,0×09,0×0D,0×0B,0×0F, 0×10,0×14,0×12,0×16,0×11,0×1,50×13,0×17, 0×18,0×1C,0×1A,0×1E,0×19,0×1D,0×1B,0×1F, 0×20,0×24,0×22,0×26,0×21,0×25,0×23,0×27, 0×28,0×2C,0×2A,0×2E,0×29,0×2D,0×2B,0×2F, 0×30,0×34,0×32,0×36,0×31,0×35,0×33,0×37, 0×38,0×3C,0×3A,0×3E,0×39,0×3D,0×3B,0×3F, 0×40,0×44,0×42,0×46,0×41,0×45,0×43,0×47, 0×48,0×4C,0×4A,0×4E,0×49,0×4D,0×4B,0×4F, 0×50,0×54,0×52,0×56,0×51,0×55,0×53,0×57, 0×58,0×5C,0×5A,0×5E,0×59,0×5D,0×5B,0×5F, 0×60,0×64,0×62,0×66,0×61,0×65,0×63,0×67, 0×68,0×6C,0×6A,0×6E,0×69,0×6D,0×6B,0×6F, 0×70,0×74,0×72,0×76,0×71,0×75,0×73,0×77, 0×78,0×7C,0×7A,0×7E,0×79,0×7D,0×7B,0×7F, 0×80,0×84,0×82,0×86,0×81,0×85,0×83,0×87, 0×88,0×8C,0×8A,0×8E,0×89,0×8D,0×8B,0×8F, 0×90,0×94,0×92,0×96,0×91,0×95,0×93,0×97, 0×98,0×9C,0×9A,0×9E,0×99,0×9D,0×9B,0×9F, 0×A0,0×A4,0×A2,0×A6,0×A1,0×A5,0×A3,0×A7, 0×A8,0×AC,0×AA,0×AE,0×A9,0×AD,0×AB,0×AF, 0×B0,0×B4,0×B2,0×B6,0×B1,0×B5,0×B3,0×B7, 0×B8,0×BC,0×BA,0×BE,0×B9,0×BD,0×BB,0×BF, 0×C0,0×C4,0×C2,0×C6,0×C1,0×C5,0×C3,0×C7, 0×C8,0×CC,0×CA,0×CE,0×C9,0×CD,0×CB,0×CF, 0×D0,0×D4,0×D2,0×D6,0×D1,0×D5,0×D3,0×D7, 0×D8,0×DC,0×DA,0×DE,0×D9,0×DD,0×DB,0×DF, 0×E0,0×E4,0×E2,0×E6,0×E1,0×E5,0×E3,0×E7, 0×E8,0×EC,0×EA,0×EE,0×E9,0×ED,0×EB,0×EF, 0×F0,0×F4,0×F2,0×F6,0×F1,0×F5,0×F3,0×F7, 0×F8,0×FC,0×FA,0×FE,0×F9,0×FD,0×FB,0×FF,

[0078] 0×00,0×08,0×04,0×0C,0×02,0×0A,0×06,0×0E, 0×01,0×09,0×05,0×0D,0×03,0×0B,0×07,0×0F, 0×10,0×18,0×14,0×1C,0×12,0×1A,0×16,0×1E, 0×11,0×19,0×15,0×1D,0×13,0×1B,0×17,0×1F, 0×20,0×28,0×24,0×2C,0×22,0×2A,0×26,0×2E, 0×21,0×29,0×25,0×2D,0×23,0×2B,0×27,0×2F, 0×30,0×38,0×34,0×3C,0×32,0×3A,0×36,0×3E, 0×31,0×39,0×35,0×3D,0×33,0×3B,0×37,0×3F, 0×40,0×48,0×44,0×4C,0×42,0×4A,0×46,0×4E, 0×41,0×49,0×45,0×4D,0×43,0×4B,0×47,0×4F, 0×50,0×58,0×54,0×5C,0×52,0×5A,0×56,0×5E, 0×51,0×59,0×55,0×5D,0×53,0×5B,0×57,0×5F, 0×60,0×68,0×64,0×6C,0×62,0×6A,0×66,0×6E, 0×61,0×69,0×65,0×6D,0×63,0×6B,0×67,0×6F, 0×70,0×78,0×74,0×7C,0×72,0×7A,0×76,0×7E, 0×71,0×79,0×75,0×7D,0×73,0×7B,0×77,0×7F, 0×80,0×88,0×84,0×8C,0×82,0×8A,0×86,0×8E, 0×81,0×89,0×85,0×8D,0×83,0×8B,0×87,0×8F, 0×90,0×98,0×94,0×9C,0×92,0×9A,0×96,0×9E, 0×91,0×99,0×95,0×9D,0×93,0×9B,0×97,0×9F, 0×A0,0×A8,0×A4,0×AC,0×A2,0×AA,0×A6,0×AE, 0×A1,0×A9,0×A5,0×AD,0×A3,0×AB,0×A7,0×AF, 0×B0,0×B8,0×B4,0×BC,0×B2,0×BA,0×B6,0×BE, 0×B1,0×B9,0×B5,0×BD,0×B3,0×BB,0×B7,0×BF, 0×C0,0×C8,0×C4,0×CC,0×C2,0×CA,0×C6,0×CE, 0×C1,0×C9,0×C5,0×CD,0×C3,0×CB,0×C7,0×CF, 0×D0,0×D8,0×D4,0×DC,0×D2,0×DA,0×D6,0×DE, 0×D1,0×D9,0×D5,0×DD,0×D3,0×DB,0×D7,0×DF, 0×E0,0×E8,0×E4,0×EC,0×E2,0×EA,0×E6,0×EE, 0×E1,0×E9,0×E5,0×ED,0×E3,0×EB,0×E7,0×EF, 0×F0,0×F8,0×F4,0×FC,0×F2,0×FA,0×F6,0×FE, 0×F1,0×F9,0×F5,0×FD,0×F3,0×FB,0×F7,0×FF,

[0079] 0×00,0×10,0×08,0×18,0×04,0×14,0×0C,0×1C, 0×02,0×12,0×0A,0×1A,0×06,0×16,0×0E,0×1E, 0×01,0×11,0×09,0×19,0×05,0×15,0×0D,0×1D, 0×03,0×13,0×0B,0×1B,0×07,0×17,0×0F,0×1F, 0×20,0×30,0×28,0×38,0×24,0×34,0×2C,0×3C, 0×22,0×32,0×2A,0×3A,0×26,0×36,0×2E,0×3E, 0×21,0×31,0×29,0×39,0×25,0×35,0×2D,0×3D, 0×23,0×33,0×2B,0×3B,0×27,0×37,0×2F,0×3F, 0×40,0×50,0×48,0×58,0×44,0×54,0×4C,0×5C, 0×42,0×52,0×4A,0×5A,0×46,0×56,0×4E,0×5E, 0×41,0×51,0×49,0×59,0×45,0×55,0×4D,0×5D, 0×43,0×53,0×4B,0×5B,0×47,0×57,0×4F,0×5F, 0×60,0×70,0×68,0×78,0×64,0×74,0×6C,0×7C, 0×62,0×72,0×6A,0×7A,0×66,0×76,0×6E,0×7E, 0×61,0×71,0×69,0×79,0×65,0×75,0×6D,0×7D, 0×63,0×73,0×6B,0×7B,0×67,0×77,0×6F,0×7F, 0×80,0×90,0×88,0×98,0×84,0×94,0×8C,0×9C, 0×82,0×92,0×8A,0×9A,0×86,0×96,0×8E,0×9E, 0×81,0×91,0×89,0×99,0×85,0×95,0×8D,0×9D, 0×83,0×93,0×8B,0×9B,0×87,0×97,0×8F,0×9F, 0×A0,0×B0,0×A8,0×B8,0×A4,0×B4,0×AC,0×BC, 0×A2,0×B2,0×AA,0×BA,0×A6,0×B6,0×AE,0×BE, 0×A1,0×B1,0×A9,0×B9,0×A5,0×B5,0×AD,0×BD, 0×A3,0×B3,0×AB,0×BB,0×A7,0×B7,0×AF,0×BF, 0×C0,0×D0,0×C8,0×D8,0×C4,0×D4,0×CC,0×DC, 0×C2,0×D2,0×CA,0×DA,0×C6,0×D6,0×CE,0×DE, 0×C1,0×D1,0×C9,0×D9,0×C5,0×D5,0×CD,0×DD, 0×C3,0×D3,0×CB,0×DB,0×C7,0×D7,0×CF,0×DF, 0×E0,0×F0,0×E8,0×F8,0×E4,0×F4,0×EC,0×FC, 0×E2,0×F2,0×EA,0×FA,0×E6,0×F6,0×EE,0×FE, 0×E1,0×F1,0×E9,0×F9,0×E5,0×F5,0×ED,0×FD, 0×E3,0×F3,0×EB,0×FB,0×E7,0×F7,0×EF,0×FF,

[0080] 0×00,0×20,0×10,0×30,0×08,0×28,0×18,0×38, 0×04,0×24,0×14,0×34,0×0C,0×2C,0×1C,0×3C, 0×02,0×22,0×12,0×32,0×0A,0×2A,0×1A,0×3A, 0×06,0×26,0×16,0×36,0×0E,0×2E,0×1E,0×3E, 0×01,0×21,0×11,0×31,0×09,0×29,0×19,0×39, 0×05,0×25,0×15,0×35,0×0D,0×2D,0×1D,0×3D, 0×03,0×23,0×13,0×33,0×0B,0×2B,0×1B,0×3B, 0×07,0×27,0×17,0×37,0×0F,0×2F,0×1F,0×3F, 0×40,0×60,0×50,0×70,0×48,0×68,0×58,0×78, 0×44,0×64,0×54,0×74,0×4C,0×6C,0×5C,0×7C, 0×42,0×62,0×52,0×72,0×4A,0×6A,0×5A,0×7A, 0×46,0×66,0×56,0×76,0×4E,0×6E,0×5E,0×7E, 0×41,0×61,0×51,0×71,0×49,0×69,0×59,0×79, 0×45,0×65,0×55,0×75,0×4D,0×6D,0×5D,0×7D, 0×43,0×63,0×53,0×73,0×4B,0×6B,0×5B,0×7B, 0×47,0×67,0×57,0×77,0×4F,0×6F,0×5F,0×7F, 0×80,0×A0,0×90,0×B0,0×88,0×A8,0×98,0×B8, 0×84,0×A4,0×94,0×B4,0×8C,0×AC,0×9C,0×BC, 0×82,0×A2,0×92,0×B2,0×8A,0×AA,0×9A,0×BA, 0×86,0×A6,0×96,0×B6,0×8E,0×AE,0×9E,0×BE, 0×81,0×A1,0×91,0×B1,0×89,0×A9,0×99,0×B9, 0×85,0×A5,0×95,0×B5,0×8D,0×AD,0×9D,0×BD, 0×83,0×A3,0×93,0×B3,0×8B,0×AB,0×9B,0×BB, 0×87,0×A7,0×97,0×B7,0×8F,0×AF,0×9F,0×BF, 0×C0,0×E0,0×D0,0×F0,0×C8,0×E8,0×D8,0×F8, 0×C4,0×E4,0×D4,0×F4,0×CC,0×EC,0×DC,0×FC, 0×C2,0×E2,0×D2,0×F2,0×CA,0×EA,0×DA,0×FA, 0×C6,0×E6,0×D6,0×F6,0×CE,0×EE,0×DE,0×FE, 0×C1,0×E1,0×D1,0×F1,0×C9,0×E9,0×D9,0×F9, 0×C5,0×E5,0×D5,0×F5,0×CD,0×ED,0×DD,0×FD, 0×C3,0×E3,0×D3,0×F3,0×CB,0×EB,0×DB,0×FB, 0×C7,0×E7,0×D7,0×F7,0×CF,0×EF,0×DF,0×FF,

[0081] 0×00,0×40,0×20,0×60,0×10,0×50,0×30,0×70, 0×08,0×48,0×28,0×68,0×18,0×58,0×38,0×78, 0×04,0×44,0×24,0×64,0×14,0×54,0×34,0×74, 0×0C,0×4C,0×2C,0×6C,0×1C,0×5C,0×3C,0×7C, 0×02,0×42,0×22,0×62,0×12,0×52,0×32,0×72, 0×0A,0×4A,0×2A,0×6A,0×1A,0×5A,0×3A,0×7A, 0×06,0×46,0×26,0×66,0×16,0×56,0×36,0×76, 0×0E,0×4E,0×2E,0×6E,0×1E,0×5E,0×3E,0×7E, 0×01,0×41,0×21,0×61,0×11,0×51,0×31,0×71, 0×09,0×49,0×29,0×69,0×19,0×59,0×39,0×79, 0×05,0×45,0×25,0×65,0×15,0×55,0×35,0×75, 0×0D,0×4D,0×2D,0×6D,0×1D,0×5D,0×3D,0×7D, 0×03,0×43,0×23,0×63,0×13,0×53,0×33,0×73, 0×0B,0×4B,0×2B,0×6B,0×1B,0×5B,0×3B,0×7B, 0×07,0×47,0×27,0×67,0×17,0×57,0×37,0×77, 0×0F,0×4F,0×2F,0×6F,0×1F,0×5F,0×3F,0×7F, 0×80,0×C0,0×A0,0×E0,0×90,0×D0,0×B0,0×F0, 0×88,0×C8,0×A8,0×E8,0×98,0×D8,0×B8,0×F8, 0×84,0×C4,0×A4,0×E4,0×94,0×D4,0×B4,0×F4, 0×8C,0×CC,0×AC,0×EC,0×9C,0×DC,0×BC,0×FC, 0×82,0×C2,0×A2,0×E2,0×92,0×D2,0×B2,0×F2, 0×8A,0×CA,0×AA,0×EA,0×9A,0×DA,0×BA,0×FA, 0×86,0×C6,0×A6,0×E6,0×96,0×D6,0×B6,0×F6, 0×8E,0×CE,0×AE,0×EE,0×9E,0×DE,0×BE,0×FE, 0×81,0×C1,0×A1,0×E1,0×91,0×D1,0×B1,0×F1, 0×89,0×C9,0×A9,0×E9,0×99,0×D9,0×B9,0×F9, 0×85,0×C5,0×A5,0×E5,0×95,0×D5,0×B5,0×F5, 0×8D,0×CD,0×AD,0×ED,0×9D,0×DD,0×BD,0×FD, 0×83,0×C3,0×A3,0×E3,0×93,0×D3,0×B3,0×F3, 0×8B,0×CB,0×AB,0×EB,0×9B,0×DB,0×BB,0×FB, 0×87,0×C7,0×A7,0×E7,0×97,0×D7,0×B7,0×F7, 0×8F,0×CF,0×AF,0×EF,0×9F,0×DF,0×BF,0×FF,

[0082] 0×00,0×80,0×40,0×C0,0×20,0×A0,0×60,0×E0, 0×10,0×90,0×50,0×D0,0×30,0×B0,0×70,0×F0, 0×08,0×88,0×48,0×C8,0×28,0×A8,0×68,0×E8, 0×18,0×98,0×58,0×D8,0×38,0×B8,0×78,0×F8, 0×04,0×84,0×44,0×C4,0×24,0×A4,0×64,0×E4, 0×14,0×94,0×54,0×D4,0×34,0×B4,0×74,0×F4, 0×0C,0×8C,0×4C,0×CC,0×2C,0×AC,0×6C,0×EC, 0×1C,0×9C,0×5C,0×DC,0×3C,0×BC,0×7C,0×FC, 0×02,0×82,0×42,0×C2,0×22,0×A2,0×62,0×E2, 0×12,0×92,0×52,0×D2,0×32,0×B2,0×72,0×F2, 0×0A,0×8A,0×4A,0×CA,0×2A,0×AA,0×6A,0×EA, 0×1A,0×9A,0×5A,0×DA,0×3A,0×BA,0×7A,0×FA, 0×06,0×86,0×46,0×C6,0×26,0×A6,0×66,0×E6, 0×16,0×96,0×56,0×D6,0×36,0×B6,0×76,0×F6, 0×0E,0×8E,0×4E,0×CE,0×2E,0×AE,0×6E,0×EE, 0×1E,0×9E,0×5E,0×DE,0×3E,0×BE,0×7E,0×FE, 0×01,0×81,0×41,0×C1,0×21 0×A1,0×61,0×E1, 0×11,0×91,0×51,0×D1,0×31,0×B1,0×71,0×F1, 0×09,0×89,0×49,0×C9,0×29,0×A9,0×69,0×E9, 0×19,0×99,0×59,0×D9,0×39,0×B9,0×79,0×F9, 0×05,0×85,0×45,0×C5,0×25,0×A5,0×65,0×E5, 0×15,0×95,0×55,0×D5,0×35,0×B5,0×75,0×F5, 0×0D,0×8D,0×4D,0×CD,0×2D,0×AD,0×6D,0×ED, 0×1D,0×9D,0×5D,0×DD,0×3D,0×bD,0×7D,0×FD, 0×03,0×83,0×43,0×C3,0×23,0×A3,0×63,0×E3, 0×13,0×93,0×53,0×D3,0×33,0×B3,0×73,0×F3, 0×0B,0×8B,0×4B,0×CB,0×2B,0×AB,0×6B,0×EB, 0×1B,0×9B,0×5B,0×DB,0×3B,0×BB,0×7B,0×FB, 0×07,0×87,0×47,0×C7,0×27,0×A7,0×67,0×E7, 0×17,0×97,0×57,0×D7,0×37,0×B7,0×77,0×F7, 0×0F,0×8F,0×4F,0×CF,0×2F,0×AF,0×6F,0×EF, 0×1F,0×9F,0×5F,0×DF,0×3F,0×BF,0×7F,0×FF