Artifact
9321b971410f1b030dd165042cf7725b61cf6362:
- File
bdelta/checksum.h
— part of check-in
[90f9b389c8]
at
2016-06-15 22:36:36
on branch trunk
— Added bdelta library stuff
(user:
bernd
size: 1227)
0000: 2f 2a 20 54 68 69 73 20 53 6f 75 72 63 65 20 43 /* This Source C
0010: 6f 64 65 20 46 6f 72 6d 20 69 73 20 73 75 62 6a ode Form is subj
0020: 65 63 74 20 74 6f 20 74 68 65 20 74 65 72 6d 73 ect to the terms
0030: 20 6f 66 20 74 68 65 20 4d 6f 7a 69 6c 6c 61 20 of the Mozilla
0040: 50 75 62 6c 69 63 0a 20 2a 20 4c 69 63 65 6e 73 Public. * Licens
0050: 65 2c 20 76 2e 20 32 2e 30 2e 20 49 66 20 61 20 e, v. 2.0. If a
0060: 63 6f 70 79 20 6f 66 20 74 68 65 20 4d 50 4c 20 copy of the MPL
0070: 77 61 73 20 6e 6f 74 20 64 69 73 74 72 69 62 75 was not distribu
0080: 74 65 64 20 77 69 74 68 20 74 68 69 73 0a 20 2a ted with this. *
0090: 20 66 69 6c 65 2c 20 59 6f 75 20 63 61 6e 20 6f file, You can o
00a0: 62 74 61 69 6e 20 6f 6e 65 20 61 74 20 68 74 74 btain one at htt
00b0: 70 3a 2f 2f 6d 6f 7a 69 6c 6c 61 2e 6f 72 67 2f p://mozilla.org/
00c0: 4d 50 4c 2f 32 2e 30 2f 2e 20 2a 2f 0a 0a 73 74 MPL/2.0/. */..st
00d0: 72 75 63 74 20 48 61 73 68 20 7b 0a 70 75 62 6c ruct Hash {.publ
00e0: 69 63 3a 0a 09 74 79 70 65 64 65 66 20 75 69 6e ic:..typedef uin
00f0: 74 36 34 5f 74 20 56 61 6c 75 65 3b 0a 09 48 61 t64_t Value;..Ha
0100: 73 68 28 29 20 7b 7d 0a 09 48 61 73 68 28 63 6f sh() {}..Hash(co
0110: 6e 73 74 20 54 6f 6b 65 6e 20 2a 62 75 66 2c 20 nst Token *buf,
0120: 75 6e 73 69 67 6e 65 64 20 62 6c 6f 63 6b 73 69 unsigned blocksi
0130: 7a 65 29 20 7b 0a 09 09 76 61 6c 75 65 20 3d 20 ze) {...value =
0140: 30 3b 0a 09 09 66 6f 72 20 28 75 6e 73 69 67 6e 0;...for (unsign
0150: 65 64 20 6e 75 6d 20 3d 20 30 3b 20 6e 75 6d 20 ed num = 0; num
0160: 3c 20 62 6c 6f 63 6b 73 69 7a 65 3b 20 2b 2b 6e < blocksize; ++n
0170: 75 6d 29 0a 09 09 09 61 64 76 61 6e 63 65 5f 61 um)....advance_a
0180: 64 64 28 62 75 66 5b 6e 75 6d 5d 29 3b 0a 09 09 dd(buf[num]);...
0190: 6f 6c 64 43 6f 65 66 66 69 63 69 65 6e 74 20 3d oldCoefficient =
01a0: 20 70 6f 77 48 61 73 68 28 6d 75 6c 74 69 70 6c powHash(multipl
01b0: 79 41 6d 6f 75 6e 74 2c 20 62 6c 6f 63 6b 73 69 yAmount, blocksi
01c0: 7a 65 29 3b 0a 09 7d 0a 09 76 6f 69 64 20 61 64 ze);..}..void ad
01d0: 76 61 6e 63 65 28 54 6f 6b 65 6e 20 6f 75 74 2c vance(Token out,
01e0: 20 54 6f 6b 65 6e 20 69 6e 29 20 7b 0a 09 09 61 Token in) {...a
01f0: 64 76 61 6e 63 65 5f 72 65 6d 6f 76 65 28 6f 75 dvance_remove(ou
0200: 74 29 3b 0a 09 09 61 64 76 61 6e 63 65 5f 61 64 t);...advance_ad
0210: 64 28 69 6e 29 3b 0a 09 7d 0a 09 73 74 61 74 69 d(in);..}..stati
0220: 63 20 75 6e 73 69 67 6e 65 64 20 6d 6f 64 75 6c c unsigned modul
0230: 6f 28 56 61 6c 75 65 20 68 61 73 68 2c 20 75 6e o(Value hash, un
0240: 73 69 67 6e 65 64 20 64 29 20 7b 0a 09 09 2f 2f signed d) {...//
0250: 20 41 73 73 75 6d 65 73 20 64 20 69 73 20 70 6f Assumes d is po
0260: 77 65 72 20 6f 66 20 32 2e 0a 09 09 72 65 74 75 wer of 2....retu
0270: 72 6e 20 68 61 73 68 20 26 20 28 64 20 2d 20 31 rn hash & (d - 1
0280: 29 3b 0a 09 7d 0a 09 56 61 6c 75 65 20 67 65 74 );..}..Value get
0290: 56 61 6c 75 65 28 29 20 7b 72 65 74 75 72 6e 20 Value() {return
02a0: 76 61 6c 75 65 20 3e 3e 20 65 78 74 72 61 50 72 value >> extraPr
02b0: 6f 63 42 69 74 73 3b 7d 0a 70 72 69 76 61 74 65 ocBits;}.private
02c0: 3a 0a 09 74 79 70 65 64 65 66 20 75 69 6e 74 36 :..typedef uint6
02d0: 34 5f 74 20 50 72 6f 63 56 61 6c 75 65 3b 0a 09 4_t ProcValue;..
02e0: 73 74 61 74 69 63 20 63 6f 6e 73 74 20 75 6e 73 static const uns
02f0: 69 67 6e 65 64 20 65 78 74 72 61 50 72 6f 63 42 igned extraProcB
0300: 69 74 73 20 3d 20 28 73 69 7a 65 6f 66 28 50 72 its = (sizeof(Pr
0310: 6f 63 56 61 6c 75 65 29 20 2d 20 73 69 7a 65 6f ocValue) - sizeo
0320: 66 28 56 61 6c 75 65 29 29 20 2a 20 38 3b 0a 0a f(Value)) * 8;..
0330: 09 73 74 61 74 69 63 20 63 6f 6e 73 74 20 50 72 .static const Pr
0340: 6f 63 56 61 6c 75 65 20 6d 75 6c 74 69 70 6c 79 ocValue multiply
0350: 41 6d 6f 75 6e 74 20 3d 20 28 31 6c 6c 20 3c 3c Amount = (1ll <<
0360: 20 65 78 74 72 61 50 72 6f 63 42 69 74 73 29 20 extraProcBits)
0370: 7c 20 31 38 31 3b 0a 09 50 72 6f 63 56 61 6c 75 | 181;..ProcValu
0380: 65 20 6f 6c 64 43 6f 65 66 66 69 63 69 65 6e 74 e oldCoefficient
0390: 2c 20 76 61 6c 75 65 3b 0a 0a 09 76 6f 69 64 20 , value;...void
03a0: 61 64 76 61 6e 63 65 5f 61 64 64 28 54 6f 6b 65 advance_add(Toke
03b0: 6e 20 69 6e 29 20 7b 0a 09 09 76 61 6c 75 65 20 n in) {...value
03c0: 2b 3d 20 69 6e 3b 0a 09 09 76 61 6c 75 65 20 2a += in;...value *
03d0: 3d 20 6d 75 6c 74 69 70 6c 79 41 6d 6f 75 6e 74 = multiplyAmount
03e0: 3b 0a 09 7d 0a 09 76 6f 69 64 20 61 64 76 61 6e ;..}..void advan
03f0: 63 65 5f 72 65 6d 6f 76 65 28 54 6f 6b 65 6e 20 ce_remove(Token
0400: 6f 75 74 29 20 7b 0a 09 09 76 61 6c 75 65 20 2d out) {...value -
0410: 3d 20 6f 75 74 20 2a 20 6f 6c 64 43 6f 65 66 66 = out * oldCoeff
0420: 69 63 69 65 6e 74 3b 0a 09 7d 0a 09 73 74 61 74 icient;..}..stat
0430: 69 63 20 50 72 6f 63 56 61 6c 75 65 20 70 6f 77 ic ProcValue pow
0440: 48 61 73 68 28 50 72 6f 63 56 61 6c 75 65 20 78 Hash(ProcValue x
0450: 2c 20 75 6e 73 69 67 6e 65 64 20 79 29 20 7b 0a , unsigned y) {.
0460: 09 09 50 72 6f 63 56 61 6c 75 65 20 72 65 73 20 ..ProcValue res
0470: 3d 20 31 3b 0a 09 09 77 68 69 6c 65 20 28 79 29 = 1;...while (y)
0480: 20 7b 0a 09 09 09 69 66 20 28 79 20 26 20 31 29 {....if (y & 1)
0490: 20 72 65 73 20 2a 3d 20 78 3b 0a 09 09 09 78 20 res *= x;....x
04a0: 2a 3d 20 78 3b 0a 09 09 09 79 20 3e 3e 3d 20 31 *= x;....y >>= 1
04b0: 3b 0a 09 09 7d 0a 09 09 72 65 74 75 72 6e 20 72 ;...}...return r
04c0: 65 73 3b 0a 09 7d 0a 7d 3b 0a 0a es;..}.};..