Skip to content

Commit b1b05ee

Browse files
xfxyjwfxfxyjwf
committed
Down-integrate from internal code base.
0 parents  commit b1b05ee

29 files changed

Lines changed: 15187 additions & 0 deletions

‎binary/arith.js‎

Lines changed: 413 additions & 0 deletions
Large diffs are not rendered by default.

‎binary/arith_test.js‎

Lines changed: 355 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,355 @@
1+
// Protocol Buffers - Google's data interchange format
2+
// Copyright 2008 Google Inc. All rights reserved.
3+
// https://developers.google.com/protocol-buffers/
4+
//
5+
// Redistribution and use in source and binary forms, with or without
6+
// modification, are permitted provided that the following conditions are
7+
// met:
8+
//
9+
// * Redistributions of source code must retain the above copyright
10+
// notice, this list of conditions and the following disclaimer.
11+
// * Redistributions in binary form must reproduce the above
12+
// copyright notice, this list of conditions and the following disclaimer
13+
// in the documentation and/or other materials provided with the
14+
// distribution.
15+
// * Neither the name of Google Inc. nor the names of its
16+
// contributors may be used to endorse or promote products derived from
17+
// this software without specific prior written permission.
18+
//
19+
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20+
// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21+
// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22+
// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23+
// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24+
// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25+
// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26+
// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27+
// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28+
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29+
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30+
31+
/**
32+
* @fileoverview Test cases for Int64-manipulation functions.
33+
*
34+
* Test suite is written using Jasmine -- see http://jasmine.github.io/
35+
*
36+
* @author cfallin@google.com (Chris Fallin)
37+
*/
38+
39+
goog.require('goog.testing.asserts');
40+
goog.require('jspb.arith.Int64');
41+
goog.require('jspb.arith.UInt64');
42+
43+
44+
describe('binaryArithTest', function() {
45+
/**
46+
* Tests comparison operations.
47+
*/
48+
it('testCompare', function() {
49+
var a = new jspb.arith.UInt64(1234, 5678);
50+
var b = new jspb.arith.UInt64(1234, 5678);
51+
assertEquals(a.cmp(b), 0);
52+
assertEquals(b.cmp(a), 0);
53+
b.lo -= 1;
54+
assertEquals(a.cmp(b), 1);
55+
assertEquals(b.cmp(a), -1);
56+
b.lo += 2;
57+
assertEquals(a.cmp(b), -1);
58+
assertEquals(b.cmp(a), 1);
59+
b.lo = a.lo;
60+
b.hi = a.hi - 1;
61+
assertEquals(a.cmp(b), 1);
62+
assertEquals(b.cmp(a), -1);
63+
64+
assertEquals(a.zero(), false);
65+
assertEquals(a.msb(), false);
66+
assertEquals(a.lsb(), false);
67+
a.hi = 0;
68+
a.lo = 0;
69+
assertEquals(a.zero(), true);
70+
a.hi = 0x80000000;
71+
assertEquals(a.zero(), false);
72+
assertEquals(a.msb(), true);
73+
a.lo = 0x00000001;
74+
assertEquals(a.lsb(), true);
75+
});
76+
77+
78+
/**
79+
* Tests shifts.
80+
*/
81+
it('testShifts', function() {
82+
var a = new jspb.arith.UInt64(1, 0);
83+
assertEquals(a.lo, 1);
84+
assertEquals(a.hi, 0);
85+
var orig = a;
86+
a = a.leftShift();
87+
assertEquals(orig.lo, 1); // original unmodified.
88+
assertEquals(orig.hi, 0);
89+
assertEquals(a.lo, 2);
90+
assertEquals(a.hi, 0);
91+
a = a.leftShift();
92+
assertEquals(a.lo, 4);
93+
assertEquals(a.hi, 0);
94+
for (var i = 0; i < 29; i++) {
95+
a = a.leftShift();
96+
}
97+
assertEquals(a.lo, 0x80000000);
98+
assertEquals(a.hi, 0);
99+
a = a.leftShift();
100+
assertEquals(a.lo, 0);
101+
assertEquals(a.hi, 1);
102+
a = a.leftShift();
103+
assertEquals(a.lo, 0);
104+
assertEquals(a.hi, 2);
105+
a = a.rightShift();
106+
a = a.rightShift();
107+
assertEquals(a.lo, 0x80000000);
108+
assertEquals(a.hi, 0);
109+
a = a.rightShift();
110+
assertEquals(a.lo, 0x40000000);
111+
assertEquals(a.hi, 0);
112+
});
113+
114+
115+
/**
116+
* Tests additions.
117+
*/
118+
it('testAdd', function() {
119+
var a = new jspb.arith.UInt64(/* lo = */ 0x89abcdef,
120+
/* hi = */ 0x01234567);
121+
var b = new jspb.arith.UInt64(/* lo = */ 0xff52ab91,
122+
/* hi = */ 0x92fa2123);
123+
// Addition with carry.
124+
var c = a.add(b);
125+
assertEquals(a.lo, 0x89abcdef); // originals unmodified.
126+
assertEquals(a.hi, 0x01234567);
127+
assertEquals(b.lo, 0xff52ab91);
128+
assertEquals(b.hi, 0x92fa2123);
129+
assertEquals(c.lo, 0x88fe7980);
130+
assertEquals(c.hi, 0x941d668b);
131+
132+
// Simple addition without carry.
133+
a.lo = 2;
134+
a.hi = 0;
135+
b.lo = 3;
136+
b.hi = 0;
137+
c = a.add(b);
138+
assertEquals(c.lo, 5);
139+
assertEquals(c.hi, 0);
140+
});
141+
142+
143+
/**
144+
* Test subtractions.
145+
*/
146+
it('testSub', function() {
147+
var kLength = 10;
148+
var hiValues = [0x1682ef32,
149+
0x583902f7,
150+
0xb62f5955,
151+
0x6ea99bbf,
152+
0x25a39c20,
153+
0x0700a08b,
154+
0x00f7304d,
155+
0x91a5b5af,
156+
0x89077fd2,
157+
0xe09e347c];
158+
var loValues = [0xe1538b18,
159+
0xbeacd556,
160+
0x74100758,
161+
0x96e3cb26,
162+
0x56c37c3f,
163+
0xe00b3f7d,
164+
0x859f25d7,
165+
0xc2ee614a,
166+
0xe1d21cd7,
167+
0x30aae6a4];
168+
for (var i = 0; i < kLength; i++) {
169+
for (var j = 0; j < kLength; j++) {
170+
var a = new jspb.arith.UInt64(loValues[i], hiValues[j]);
171+
var b = new jspb.arith.UInt64(loValues[j], hiValues[i]);
172+
var c = a.add(b).sub(b);
173+
assertEquals(c.hi, a.hi);
174+
assertEquals(c.lo, a.lo);
175+
}
176+
}
177+
});
178+
179+
180+
/**
181+
* Tests 32-by-32 multiplication.
182+
*/
183+
it('testMul32x32', function() {
184+
var testData = [
185+
// a b low(a*b) high(a*b)
186+
[0xc0abe2f8, 0x1607898a, 0x5de711b0, 0x109471b8],
187+
[0x915eb3cb, 0x4fb66d0e, 0xbd0d441a, 0x2d43d0bc],
188+
[0xfe4efe70, 0x80b48c37, 0xbcddea10, 0x7fdada0c],
189+
[0xe222fd4a, 0xe43d524a, 0xd5e0eb64, 0xc99d549c],
190+
[0xd171f469, 0xb94ebd01, 0x4be17969, 0x979bc4fa],
191+
[0x829cc1df, 0xe2598b38, 0xf4157dc8, 0x737c12ad],
192+
[0xf10c3767, 0x8382881e, 0x942b3612, 0x7bd428b8],
193+
[0xb0f6dd24, 0x232597e1, 0x079c98a4, 0x184bbce7],
194+
[0xfcdb05a7, 0x902f55bc, 0x636199a4, 0x8e69f412],
195+
[0x0dd0bfa9, 0x916e27b1, 0x6e2542d9, 0x07d92e65]
196+
];
197+
198+
for (var i = 0; i < testData.length; i++) {
199+
var a = testData[i][0] >>> 0;
200+
var b = testData[i][1] >>> 0;
201+
var cLow = testData[i][2] >>> 0;
202+
var cHigh = testData[i][3] >>> 0;
203+
var c = jspb.arith.UInt64.mul32x32(a, b);
204+
assertEquals(c.lo, cLow);
205+
assertEquals(c.hi, cHigh);
206+
}
207+
});
208+
209+
210+
/**
211+
* Tests 64-by-32 multiplication.
212+
*/
213+
it('testMul', function() {
214+
// 64x32 bits produces 96 bits of product. The multiplication function under
215+
// test truncates the top 32 bits, so we compare against a 64-bit expected
216+
// product.
217+
var testData = [
218+
// low(a) high(a) low(a*b) high(a*b)
219+
[0xec10955b, 0x360eb168, 0x4b7f3f5b, 0xbfcb7c59, 0x9517da5f],
220+
[0x42b000fc, 0x9d101642, 0x6fa1ab72, 0x2584c438, 0x6a9e6d2b],
221+
[0xf42d4fb4, 0xae366403, 0xa65a1000, 0x92434000, 0x1ff978df],
222+
[0x17e2f56b, 0x25487693, 0xf13f98c7, 0x73794e2d, 0xa96b0c6a],
223+
[0x492f241f, 0x76c0eb67, 0x7377ac44, 0xd4336c3c, 0xfc4b1ebe],
224+
[0xd6b92321, 0xe184fa48, 0xd6e76904, 0x93141584, 0xcbf44da1],
225+
[0x4bf007ea, 0x968c0a9e, 0xf5e4026a, 0x4fdb1ae4, 0x61b9fb7d],
226+
[0x10a83be7, 0x2d685ba6, 0xc9e5fb7f, 0x2ad43499, 0x3742473d],
227+
[0x2f261829, 0x1aca681a, 0x3d3494e3, 0x8213205b, 0x283719f8],
228+
[0xe4f2ce21, 0x2e74b7bd, 0xd801b38b, 0xbc17feeb, 0xc6c44e0f]
229+
];
230+
231+
for (var i = 0; i < testData.length; i++) {
232+
var a = new jspb.arith.UInt64(testData[i][0], testData[i][1]);
233+
var prod = a.mul(testData[i][2]);
234+
assertEquals(prod.lo, testData[i][3]);
235+
assertEquals(prod.hi, testData[i][4]);
236+
}
237+
});
238+
239+
240+
/**
241+
* Tests 64-div-by-32 division.
242+
*/
243+
it('testDiv', function() {
244+
// Compute a/b, yielding quot = a/b and rem = a%b.
245+
var testData = [
246+
// --- divisors in (0, 2^32-1) to test full divisor range
247+
// low(a) high(a) b low(quot) high(quot) rem
248+
[0x712443f1, 0xe85cefcc, 0xc1a7050b, 0x332c79ad, 0x00000001, 0x92ffa882],
249+
[0x11912915, 0xb2699eb5, 0x30467cbe, 0xb21b4be4, 0x00000003, 0x283465dd],
250+
[0x0d917982, 0x201f2a6e, 0x3f35bf03, 0x8217c8e4, 0x00000000, 0x153402d6],
251+
[0xa072c108, 0x74020c96, 0xc60568fd, 0x95f9613e, 0x00000000, 0x3f4676c2],
252+
[0xd845d5d8, 0xcdd235c4, 0x20426475, 0x6154e78b, 0x00000006, 0x202fb751],
253+
[0xa4dbf71f, 0x9e90465e, 0xf08e022f, 0xa8be947f, 0x00000000, 0xbe43b5ce],
254+
[0x3dbe627f, 0xa791f4b9, 0x28a5bd89, 0x1f5dfe93, 0x00000004, 0x02bf9ed4],
255+
[0x5c1c53ee, 0xccf5102e, 0x198576e7, 0x07e3ae31, 0x00000008, 0x02ea8fb7],
256+
[0xfef1e581, 0x04714067, 0xca6540c1, 0x059e73ec, 0x00000000, 0x31658095],
257+
[0x1e2dd90c, 0x13dd6667, 0x8b2184c3, 0x248d1a42, 0x00000000, 0x4ca6d0c6],
258+
// --- divisors in (0, 2^16-1) to test larger quotient high-words
259+
// low(a) high(a) b low(quot) high(quot) rem
260+
[0x86722b47, 0x2cd57c9a, 0x00003123, 0x2ae41b7a, 0x0000e995, 0x00000f99],
261+
[0x1dd7884c, 0xf5e839bc, 0x00009eeb, 0x5c886242, 0x00018c21, 0x000099b6],
262+
[0x5c53d625, 0x899fc7e5, 0x000087d7, 0xd625007a, 0x0001035c, 0x000019af],
263+
[0x6932d932, 0x9d0a5488, 0x000051fb, 0x9d976143, 0x0001ea63, 0x00004981],
264+
[0x4d18bb85, 0x0c92fb31, 0x00001d9f, 0x03265ab4, 0x00006cac, 0x000001b9],
265+
[0xbe756768, 0xdea67ccb, 0x00008a03, 0x58add442, 0x00019cff, 0x000056a2],
266+
[0xe2466f9a, 0x2521f114, 0x0000c350, 0xa0c0860d, 0x000030ab, 0x0000a48a],
267+
[0xf00ddad1, 0xe2f5446a, 0x00002cfc, 0x762697a6, 0x00050b96, 0x00000b69],
268+
[0xa879152a, 0x0a70e0a5, 0x00007cdf, 0xb44151b3, 0x00001567, 0x0000363d],
269+
[0x7179a74c, 0x46083fff, 0x0000253c, 0x4d39ba6e, 0x0001e17f, 0x00000f84]
270+
];
271+
272+
for (var i = 0; i < testData.length; i++) {
273+
var a = new jspb.arith.UInt64(testData[i][0], testData[i][1]);
274+
var result = a.div(testData[i][2]);
275+
var quotient = result[0];
276+
var remainder = result[1];
277+
assertEquals(quotient.lo, testData[i][3]);
278+
assertEquals(quotient.hi, testData[i][4]);
279+
assertEquals(remainder.lo, testData[i][5]);
280+
}
281+
});
282+
283+
284+
/**
285+
* Tests .toString() and .fromString().
286+
*/
287+
it('testStrings', function() {
288+
var testData = [
289+
[0x5e84c935, 0xcae33d0e, '14619595947299359029'],
290+
[0x62b3b8b8, 0x93480544, '10612738313170434232'],
291+
[0x319bfb13, 0xc01c4172, '13843011313344445203'],
292+
[0x5b8a65fb, 0xa5885b31, '11927883880638080507'],
293+
[0x6bdb80f1, 0xb0d1b16b, '12741159895737008369'],
294+
[0x4b82b442, 0x2e0d8c97, '3318463081876730946'],
295+
[0x780d5208, 0x7d76752c, '9040542135845999112'],
296+
[0x2e46800f, 0x0993778d, '690026616168284175'],
297+
[0xf00a7e32, 0xcd8e3931, '14811839111111540274'],
298+
[0x1baeccd6, 0x923048c4, '10533999535534820566'],
299+
[0x03669d29, 0xbff3ab72, '13831587386756603177'],
300+
[0x2526073e, 0x01affc81, '121593346566522686'],
301+
[0xc24244e0, 0xd7f40d0e, '15561076969511732448'],
302+
[0xc56a341e, 0xa68b66a7, '12000798502816461854'],
303+
[0x8738d64d, 0xbfe78604, '13828168534871037517'],
304+
[0x5baff03b, 0xd7572aea, '15516918227177304123'],
305+
[0x4a843d8a, 0x864e132b, '9677693725920476554'],
306+
[0x25b4e94d, 0x22b54dc6, '2500990681505655117'],
307+
[0x6bbe664b, 0x55a5cc0e, '6171563226690381387'],
308+
[0xee916c81, 0xb00aabb3, '12685140089732426881']
309+
];
310+
311+
for (var i = 0; i < testData.length; i++) {
312+
var a = new jspb.arith.UInt64(testData[i][0], testData[i][1]);
313+
var roundtrip = jspb.arith.UInt64.fromString(a.toString());
314+
assertEquals(roundtrip.lo, a.lo);
315+
assertEquals(roundtrip.hi, a.hi);
316+
assertEquals(a.toString(), testData[i][2]);
317+
}
318+
});
319+
320+
321+
/**
322+
* Tests signed Int64s. These are built on UInt64s, so we only need to test
323+
* the explicit overrides: .toString() and .fromString().
324+
*/
325+
it('testSignedInt64', function() {
326+
var testStrings = [
327+
'-7847499644178593666',
328+
'3771946501229139523',
329+
'2872856549054995060',
330+
'-5780049594274350904',
331+
'3383785956695105201',
332+
'2973055184857072610',
333+
'-3879428459215627206',
334+
'4589812431064156631',
335+
'8484075557333689940',
336+
'1075325817098092407',
337+
'-4346697501012292314',
338+
'2488620459718316637',
339+
'6112655187423520672',
340+
'-3655278273928612104',
341+
'3439154019435803196',
342+
'1004112478843763757',
343+
'-6587790776614368413',
344+
'664320065099714586',
345+
'4760412909973292912',
346+
'-7911903989602274672'
347+
];
348+
349+
for (var i = 0; i < testStrings.length; i++) {
350+
var roundtrip =
351+
jspb.arith.Int64.fromString(testStrings[i]).toString();
352+
assertEquals(roundtrip, testStrings[i]);
353+
}
354+
});
355+
});

0 commit comments

Comments
 (0)