/
adler_test.c
121 lines (99 loc) · 3.38 KB
/
adler_test.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
/*
* Copyright (C) 1995-2011, 2016 Mark Adler
* For conditions of distribution and use, see copyright notice in zlib.h
*
* Changes:
* nx_adler_combine.c derived from adler32.c in zlib 1.2.11.
* External function names prefixed with nx_ to prevent zlib name collisions
*/
#include <stdint.h>
#define BASE 65521U /* largest prime smaller than 65536 */
#define MOD(a) a %= BASE
#define MOD63(a) a %= BASE
/* ========================================================================= */
unsigned long nx_adler32_combine(adler1, adler2, len2)
unsigned long adler1;
unsigned long adler2;
uint64_t len2; /* z_off64_t len2; */
{
unsigned long sum1;
unsigned long sum2;
unsigned rem;
/* for negative len, return invalid adler32 as a clue for debugging */
if (len2 < 0)
return 0xffffffffUL;
/* the derivation of this formula is left as an exercise for the reader */
MOD63(len2); /* assumes len2 >= 0 */
rem = (unsigned)len2;
sum1 = adler1 & 0xffff;
sum2 = rem * sum1;
MOD(sum2);
sum1 += (adler2 & 0xffff) + BASE - 1;
sum2 += ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - rem;
if (sum1 >= BASE) sum1 -= BASE;
if (sum1 >= BASE) sum1 -= BASE;
// why?
if (sum2 >= ((unsigned long)BASE << 1)) sum2 -= ((unsigned long)BASE << 1);
if (sum2 >= BASE) sum2 -= BASE;
return sum1 | (sum2 << 16);
}
/* ========================================================================= */
unsigned long new_adler32_combine(adler1, adler2, len2)
unsigned long adler1;
unsigned long adler2;
uint64_t len2; /* z_off64_t len2; */
{
unsigned long sum1;
unsigned long sum2;
unsigned rem;
#define MYMOD(X) ((X)%BASE)
// https://en.wikipedia.org/wiki/Adler-32
/* subract 1 because a = 1 initially */
//sum1 = MYMOD( (adler1 & 0xffff) + (adler2 & 0xffff) - 1 );
sum1 = (adler1 & 0xffff) + (adler2 & 0xffff) + BASE - 1;
if (sum1 >= BASE) sum1 -= BASE;
if (sum1 >= BASE) sum1 -= BASE;
//sum1 = MYMOD( (adler1 & 0xffff) + (adler2 & 0xffff) + BASE - 1 );
// a is added to b len2 times
sum2 = MYMOD( MYMOD(len2) * (adler1 & 0xffff) );
//sum2 = MYMOD( len2 * (adler1 & 0xffff) );
sum2 = sum2 + ((adler1 >> 16) & 0xffff) + ((adler2 >> 16) & 0xffff) + BASE - MYMOD(len2) ;
sum2 = sum2 % (2*BASE);
sum2 = MYMOD(sum2);
return sum1 | (sum2 << 16);
}
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
void adler_experiment1()
{
unsigned long adler1, adler2;
uint64_t len;
adler1 = 1;
adler2 = 0x12345678;
len = 500;
printf("ad1 %lx ad2 %lx len %ld combine %lx\n", adler1, adler2, len, nx_adler32_combine(adler1, adler2, len));
}
int main()
{
long a,b,len;
adler_experiment1();
return 0;
#if 0
for(a=1; a<(10*BASE); a++)
for(b=1; b<(10*BASE); b++)
for(len=1; len<1000; len++) {
assert( nx_adler32_combine(a,b,len) == new_adler32_combine(a,b,len) );
// printf("%lx %lx %ld\n", nx_adler32_combine(a,b,len), new_adler32_combine(a,b,len), len );
}
#else
while(1) {
a = 0xFFFFFFFFUL & lrand48();
b = 0xFFFFFFFFUL & lrand48();
len = 0xFFFFFFFUL & lrand48();
if( nx_adler32_combine(a,b,len) != new_adler32_combine(a,b,len) )
printf("%lx %lx %lx %lx %ld\n", nx_adler32_combine(a,b,len), new_adler32_combine(a,b,len), a, b, len );
}
#endif
return 0;
}