Patent GB-1494750-A (GB)
Title: Data processing system with hash instruction
IPC: G06F9/22
Filed: 1974-12-12
Abstract: 1494750 Data processing HONEYWELL INFORMATION SYSTEMS Inc 12 Dec 1974 [13 Dec 1973] 53774/74 Heading G4A In a data processing system a hash instruction results in a data descriptor specified by the instruction being accessed, the descriptor including the address of an operand and a characteristic of it (e.g. its length), the operand being fetched and used in conjunction with the characteristic to compute a hash address. As described the contents of a circulating register are shifted left before a four byte unit of the operand is added to it, the result being one's complemented and shifted left again before the same four byte unit is added, this process being repeated until all the four byte units specified by the length characteristic have been operated on. Data processing system.-The system comprises four semi-conductor memory modules (201, Fig. 2, not shown) interfaced via a sequencer (202) to an input/output controller (220) controlling, e.g. tape or disc stores and a CPU (200) the latter including a read only microprogram store (210), a data management unit (206), an address control unit (207) and an ALU (212). A buffer (204) stores the most recently or most frequently used data in the form of pages, a directory (205) keeping an index of pages in the store (204), address control unit (207) including an associative store with the base addresses of the most recently used memory segments and their segment number. Operation.-A hash instruction comprising an 8 bit op code (bits 0-7), 4 bit general register code (8-11) and a 20 bit address syllable (bits 12-31) is stored in an instruction register 400 (Fig. 4) of instruction set unit 208. The op code results in control store units 210 performing tests to determine (1) that bit 11 of the instruction is zero (since two registers are required for hash instruction), (2) whether bit 12 indicates direct or indirect addressing. The address syllable is used to fetch a data descriptor having a tag field of 01 indicating that a second (extended) descriptor is also to be fetched. The first descriptor contains the segment (STN, STE) and displacement (DISP) within the segment of the operand and the second which describes characteristics of the operand (e.g. type of coding, length) is transferred to register 408, bits 40-47 being fed to register 412 for comparison with predetermined constants loaded by the control store unit into register 414 to determine whether the data type is correct for "hashing", an illegal data type exception or a termination routine occurring otherwise. Hash operation.-If the data type is correct the hash operation is performed (flow drawing of Fig. 5). First bits 56-63 of the descriptor (representing the number of bytes of the operands) are accessed. The hash instruction operates on groups of 4 bytes, the number of groups of 4 bytes being stored in a register N of store 406 with the remainder in a register R. The absolute address of the operand is then developed and entered into a register S. The first 4 bytes of the operand are fetched and stored in register 422, the valve N is decremented by 1 and the address incremented by 4. The contents of circulation register 420 are rotated left 19 bits and the content of register 422 added to it, the result being replaced after one's complementing in register 420 (any carry being added to the lowermost bit). The register is then rotated left 18 bits and the contents of register 422 added to it. This process is repeated until N=0. The remainder bytes are then processed by first adding zeroes to make the remainder up to 4 bytes and then repeating the above process. Finally the contents of register 420 are rotated left 17 bits, added to the contents of register 422 with any overflow being added to the lowest bit, the result being. stored in a register specified by the instruction. This register now holds the random key address identifying the storage location for the left record in secondary storage, e.g. disc. A multiplication or division operation is executed to specify the page in which the record is to be stored.