# US 10,372,695 B2 · Technologies for computing rolling hashes > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,372,695 B2 - Document ID: US10372695B2 - Status: Granted - Kind: B2 - Application number: 14/583,669 - Filed: 2014-12-27 - Published: 2016-06-30 - Granted: 2019-08-06 - Earliest claimed: 2014-12-27 - Assignees: Intel Corporation - Applicants: Intel Corporation - Inventors: James D. Guilford; Vinodh Gopal; Gregory B. Tucker - Web page: https://patentgrep.com/patent/US10372695B2 ## CPC - G06F 16/2255: {Hash tables} - G06F 16/1748: {De-duplication implemented within the file system, e.g. based on file segments (de-duplication techniques in storage systems for the management of data blocks G06F3/0641)} - G06F 16/2365: {Ensuring data consistency and integrity} - H03M 7/3091: {Data deduplication} - H03M 7/6047: {Power optimization with respect to the encoder, decoder, storage or transmission} - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - H03M: CODING; DECODING; CODE CONVERSION IN GENERAL (using fluidic means F15C4/00; optical analogue/digital converters G02F7/00; coding, decoding or code conversion, specially adapted for particular applications, see the relevant subclasses, e.g. G01D, G01R, G06F, G06T, G09G, G10L, G11B, G11C, H04B, H04L, H04M, H04N; ciphering or deciphering for cryptography or other purposes involving the need for secrecy G09C) ## Abstract Technologies for computing rolling hashes include a computing device having a first hash table that includes a first plurality of random-valued entries and a second hash table that includes a second plurality of random-valued entries. The computing device retrieves a block of data from a data buffer and generates a hash based on the block of data, a previously generated hash, the first hash table, and the second hash table. The computing device further determines whether the generated hash matches a predefined trigger and records a data boundary in response to a determination that the generated hash matches the trigger. ## Claims ### Claim 1 A computing device for computing rolling hashes during identification of one or more data chunks to de-duplicate in a data de-duplication operation, the computing device comprising: one or more processors; and a memory storing a plurality of instructions, which, when executed on the one or more processors, cause the computing device to: retrieve, as part of the data de-duplication operation in the memory, a block of data from a data buffer; generate, by the one or more processors, a hash based on the block of data, a previously generated hash, a first hash table initialized with a first plurality of random-valued entries, and a second hash table initialized with a second plurality of random-valued entries, wherein the second plurality of random-valued entries is the first plurality of random-valued entries rotated by a number of table indices equal to a hash window size of a hash algorithm; determine whether the generated hash matches a predefined trigger; record a data boundary in response to a determination that the generated hash matches the trigger, wherein the data boundary is indicative of a data chunk to de-duplicate; de-duplicate the data chunk using the recorded data boundary as input; and store a result of the de-duplication of the data chunk in the memory. ### Claim 2 (depends on 1) The computing device of claim 1, wherein to retrieve the block of data from the data buffer comprises to retrieve a next byte of data from the data buffer. ### Claim 3 (depends on 1) The computing device of claim 1, wherein to generate the hash comprises to generate a hash based on rotation and exclusive-or bitwise operations. ### Claim 4 (depends on 1) The computing device of claim 1, wherein to generate the hash comprises to generate a hash according to hash=(hashprev «<1)^table1[buf[i]]^table2[buf[i−w]]; wherein hashprev is the previously generated hash; wherein hashprev<<<1 denotes bitwise rotation of the previously generated hash; wherein ^ denotes an exclusive-or bitwise operation; wherein w is the hash window size of the hash algorithm; wherein buf[i] is the retrieved block of data of the data buffer; wherein buf[i−w] is a previous block of data of the data buffer offset by an index difference equal to the hash window size; wherein table1[buf[i]] is the random-valued entry of the first hash table corresponding with the retrieved block of data; and wherein table2[buf[i−w]] is the random-valued entry of the second hash table corresponding with the previous block of data. ### Claim 5 (depends on 1) The computing device of claim 1, wherein to determine whether the generated hash matches the predefined trigger comprises to apply a bitmask to the generated hash. ### Claim 6 (depends on 1) The computing device of claim 1, wherein to record the data boundary comprises to record a data de-duplication boundary that defines a boundary of a data chunk for the data de-duplication. ### Claim 7 (depends on 1) The computing device of claim 1, wherein the plurality of instructions further causes the computing device to determine an initial hash value. ### Claim 8 (depends on 7) The computing device of claim 7, wherein the initial hash value is indicative of a value at which to start the rolling hashes. ### Claim 9 (depends on 1) The computing device of claim 1, wherein the plurality of instructions further causes the computing device to initialize a rolling hash algorithm to generate the hash. ### Claim 10 (depends on 9) The computing device of claim 9, wherein to initialize the rolling hash algorithm comprises to determine a size of the data buffer. ### Claim 11 (depends on 9) The computing device of claim 9, wherein to initialize the rolling hash algorithm comprises to determine a hash window size of the hash algorithm. ### Claim 12 (depends on 9) The computing device of claim 9, wherein to initialize the rolling hash algorithm comprises to determine a bitmask and the trigger associated with the data boundary. ### Claim 13 One or more non-transitory machine-readable storage media comprising a plurality of instructions stored thereon that, in response to execution by a computing device, cause the computing device to: retrieve, as part of a data de-duplication operation in a memory of the computing device, a block of data from a data buffer; generate, by one or more processors, a hash based on the block of data, a previously generated hash, a first hash table initialized with a first plurality of random-valued entries, and a second hash table initialized with a second plurality of random-valued entries, wherein the second plurality of random-valued entries is the first plurality of random-valued entries rotated by a number of table indices equal to a hash window size of a hash algorithm; determine whether the generated hash matches a predefined trigger; record a data boundary in response to a determination that the generated hash matches the trigger, wherein the data boundary is indicative of a data chunk to de-duplicate; de-duplicate the data chunk using the recorded data boundary as input; and store a result of the de-duplication of the data chunk in the memory of the computing device. ### Claim 14 (depends on 13) The one or more non-transitory machine-readable storage media of claim 13, wherein to retrieve the block of data from the data buffer comprises to retrieve a next byte of data from the data buffer. ### Claim 15 (depends on 13) The one or more non-transitory machine-readable storage media of claim 13, wherein the second hash table includes the random-valued entries of the first hash table rotated by a number of table indices equal to a hash window size of a hash algorithm for generating the hash; wherein to generate the hash comprises to generate a hash according to hash=(hashprev<<<1) A table1[buf[i]]^table2[buf[i−w]]; wherein hashprev is the previously generated hash; wherein hashprev<<<1 denotes bitwise rotation of the previously generated hash; wherein ^ denotes an exclusive-or bitwise operation; wherein w is the hash window size of the hash algorithm; wherein buf[i] is the retrieved block of data of the data buffer; wherein buf[i−w] is a previous block of data of the data buffer offset by an index difference equal to the hash window size; wherein table1[buf[i]] is the random-valued entry of the first hash table corresponding with the retrieved block of data; and wherein table2[buf[i−w]] is the random-valued entry of the second hash table corresponding with the previous block of data. ### Claim 16 (depends on 13) The one or more non-transitory machine-readable storage media of claim 13, wherein to determine whether the generated hash matches the predefined trigger comprises to apply a bitmask to the generated hash. ### Claim 17 (depends on 13) The one or more non-transitory machine-readable storage media of claim 13, wherein the plurality of instructions further cause the computing device to initialize a rolling hash algorithm to generate the hash. ### Claim 18 (depends on 17) The one or more non-transitory machine-readable storage media of claim 17, wherein to initialize the rolling hash algorithm comprises to determine a size of the data buffer. ### Claim 19 (depends on 17) The one or more non-transitory machine-readable storage media of claim 17, wherein to initialize the rolling hash algorithm comprises to determine a hash window size of the hash algorithm. ### Claim 20 (depends on 17) The one or more non-transitory machine-readable storage media of claim 17, wherein to initialize the rolling hash algorithm comprises to determine a bitmask and the trigger associated with the data boundary. ### Claim 21 A method for computing rolling hashes by a computing device during identification of one or more data chunks in memory to de-duplicate in a data de-duplication operation, the method comprising: retrieving, by the computing device as part of the data de-duplication operation in the memory, a block of data from a data buffer; generating, by one or more processors of the computing device, a hash based on the block of data, a previously generated hash, a first hash table initialized with a first plurality of random-valued entries, and a second hash table initialized with a second plurality of random-valued entries, wherein the second plurality of random-valued entries is the first plurality of random-valued entries rotated by a number of table indices equal to a hash window size of a hash algorithm; determining, by the computing device, whether the generated hash matches a predefined trigger; recording, by the computing device, a data boundary in response to determining that the generated hash matches the trigger, wherein the data boundary is indicative of a data chunk to de-duplicate; de-duplicating the data chunk using the recorded data boundary as input; and storing a result of the de-duplication of the data chunk in a memory of the computing device. ### Claim 22 (depends on 21) The method of claim 21, wherein retrieving the block of data from the data buffer comprises retrieving a next byte of data from the data buffer. ### Claim 23 (depends on 21) The method of claim 21, wherein the second hash table includes the random-valued entries of the first hash table rotated by a number of table indices equal to a hash window size of a hash algorithm for generating the hash; wherein generating the hash comprises generating a hash according to hash=(hashprev<<<1) A table1[buf[i]]^table2[buf[i−w]]; wherein hashprev is the previously generated hash; wherein hashprev<<<1 denotes bitwise rotation of the previously generated hash; wherein ^ denotes an exclusive-or bitwise operation; wherein w is the hash window size of the hash algorithm; wherein buf[i] is the retrieved block of data of the data buffer; wherein buf[i−w] is a previous block of data of the data buffer offset by an index difference equal to the hash window size; wherein table1[buf[i]] is the random-valued entry of the first hash table corresponding with the retrieved block of data; and wherein table2[buf[i−w]] is the random-valued entry of the second hash table corresponding with the previous block of data.