adler32.c 4.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180
  1. /* adler32.c -- compute the Adler-32 checksum of a data stream
  2. * Copyright (C) 1995-2011 Mark Adler
  3. * For conditions of distribution and use, see copyright notice in zlib.h
  4. */
  5. /* @(#) $Id$ */
  6. #include "zutil.h"
  7. #define local static
  8. local uLong adler32_combine_ OF((uLong adler1, uLong adler2, z_off64_t len2));
  9. #define BASE 65521 /* largest prime smaller than 65536 */
  10. #define NMAX 5552
  11. /* NMAX is the largest n such that 255n(n+1)/2 + (n+1)(BASE-1) <= 2^32-1 */
  12. #define DO1(buf,i) {adler += (buf)[i]; sum2 += adler;}
  13. #define DO2(buf,i) DO1(buf,i); DO1(buf,i+1);
  14. #define DO4(buf,i) DO2(buf,i); DO2(buf,i+2);
  15. #define DO8(buf,i) DO4(buf,i); DO4(buf,i+4);
  16. #define DO16(buf) DO8(buf,0); DO8(buf,8);
  17. /* use NO_DIVIDE if your processor does not do division in hardware --
  18. try it both ways to see which is faster */
  19. #ifdef NO_DIVIDE
  20. /* note that this assumes BASE is 65521, where 65536 % 65521 == 15
  21. (thank you to John Reiser for pointing this out) */
  22. # define CHOP(a) \
  23. do { \
  24. unsigned long tmp = a >> 16; \
  25. a &= 0xffffUL; \
  26. a += (tmp << 4) - tmp; \
  27. } while (0)
  28. # define MOD28(a) \
  29. do { \
  30. CHOP(a); \
  31. if (a >= BASE) a -= BASE; \
  32. } while (0)
  33. # define MOD(a) \
  34. do { \
  35. CHOP(a); \
  36. MOD28(a); \
  37. } while (0)
  38. # define MOD63(a) \
  39. do { /* this assumes a is not negative */ \
  40. z_off64_t tmp = a >> 32; \
  41. a &= 0xffffffffL; \
  42. a += (tmp << 8) - (tmp << 5) + tmp; \
  43. tmp = a >> 16; \
  44. a &= 0xffffL; \
  45. a += (tmp << 4) - tmp; \
  46. tmp = a >> 16; \
  47. a &= 0xffffL; \
  48. a += (tmp << 4) - tmp; \
  49. if (a >= BASE) a -= BASE; \
  50. } while (0)
  51. #else
  52. # define MOD(a) a %= BASE
  53. # define MOD28(a) a %= BASE
  54. # define MOD63(a) a %= BASE
  55. #endif
  56. /* ========================================================================= */
  57. uLong ZEXPORT adler32(adler, buf, len)
  58. uLong adler;
  59. const Bytef *buf;
  60. uInt len;
  61. {
  62. unsigned long sum2;
  63. unsigned n;
  64. /* split Adler-32 into component sums */
  65. sum2 = (adler >> 16) & 0xffff;
  66. adler &= 0xffff;
  67. /* in case user likes doing a byte at a time, keep it fast */
  68. if (len == 1) {
  69. adler += buf[0];
  70. if (adler >= BASE)
  71. adler -= BASE;
  72. sum2 += adler;
  73. if (sum2 >= BASE)
  74. sum2 -= BASE;
  75. return adler | (sum2 << 16);
  76. }
  77. /* initial Adler-32 value (deferred check for len == 1 speed) */
  78. if (buf == Z_NULL)
  79. return 1L;
  80. /* in case short lengths are provided, keep it somewhat fast */
  81. if (len < 16) {
  82. while (len--) {
  83. adler += *buf++;
  84. sum2 += adler;
  85. }
  86. if (adler >= BASE)
  87. adler -= BASE;
  88. MOD28(sum2); /* only added so many BASE's */
  89. return adler | (sum2 << 16);
  90. }
  91. /* do length NMAX blocks -- requires just one modulo operation */
  92. while (len >= NMAX) {
  93. len -= NMAX;
  94. n = NMAX / 16; /* NMAX is divisible by 16 */
  95. do {
  96. DO16(buf); /* 16 sums unrolled */
  97. buf += 16;
  98. } while (--n);
  99. MOD(adler);
  100. MOD(sum2);
  101. }
  102. /* do remaining bytes (less than NMAX, still just one modulo) */
  103. if (len) { /* avoid modulos if none remaining */
  104. while (len >= 16) {
  105. len -= 16;
  106. DO16(buf);
  107. buf += 16;
  108. }
  109. while (len--) {
  110. adler += *buf++;
  111. sum2 += adler;
  112. }
  113. MOD(adler);
  114. MOD(sum2);
  115. }
  116. /* return recombined sums */
  117. return adler | (sum2 << 16);
  118. }
  119. /* ========================================================================= */
  120. local uLong adler32_combine_(adler1, adler2, len2)
  121. uLong adler1;
  122. uLong adler2;
  123. z_off64_t len2;
  124. {
  125. unsigned long sum1;
  126. unsigned long sum2;
  127. unsigned rem;
  128. /* for negative len, return invalid adler32 as a clue for debugging */
  129. if (len2 < 0)
  130. return 0xffffffffUL;
  131. /* the derivation of this formula is left as an exercise for the reader */
  132. MOD63(len2); /* assumes len2 >= 0 */
  133. rem = (unsigned)len2;
  134. sum1 = adler1 & 0xffff;
  135. sum2 = rem * sum1;
  136. MOD(sum2);
  137. sum1 += (adler2 & 0xffff) + BASE - 1;
  138. sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
  139. if (sum1 >= BASE) sum1 -= BASE;
  140. if (sum1 >= BASE) sum1 -= BASE;
  141. if (sum2 >= (BASE << 1)) sum2 -= (BASE << 1);
  142. if (sum2 >= BASE) sum2 -= BASE;
  143. return sum1 | (sum2 << 16);
  144. }
  145. /* ========================================================================= */
  146. uLong ZEXPORT adler32_combine(adler1, adler2, len2)
  147. uLong adler1;
  148. uLong adler2;
  149. z_off_t len2;
  150. {
  151. return adler32_combine_(adler1, adler2, len2);
  152. }
  153. uLong ZEXPORT adler32_combine64(adler1, adler2, len2)
  154. uLong adler1;
  155. uLong adler2;
  156. z_off64_t len2;
  157. {
  158. return adler32_combine_(adler1, adler2, len2);
  159. }