Fix encoding/decoding of base-256 numbers

justfalter · justfalter · commit c80341a5686e · 2019-05-30T11:30:45.000-05:00
- Encoding/decoding of base-256 numbers failed to failed to handle last
byte in buffer. Handling was previously broken.
- Take javascript's MAX_SAFE_INTEGER / MIN_SAFE_INTEGER into account
when encoding/decoding. Namely, if the numbers cannot accurately be
represented in javascript with integer-precision, a TypeError will be
thrown.
- Throw a TypeError if the parser is passed an buffer that does not
appear to be base-256 encoded. (must start with 0x80 or 0xff)
diff --git a/lib/large-numbers.js b/lib/large-numbers.js
@@ -1,12 +1,13 @@
 'use strict'
 // Tar can encode large and negative numbers using a leading byte of
-// 0xff for negative, and 0x80 for positive.  The trailing byte in the
-// section will always be 0x20, or in some implementations 0x00.
-// this module encodes and decodes these things.
+// 0xff for negative, and 0x80 for positive.
 
 const encode = exports.encode = (num, buf) => {
-  buf[buf.length - 1] = 0x20
-  if (num < 0)
+  if (!Number.isSafeInteger(num))
+    // The number is so large that javascript cannot represent it with integer
+    // precision.
+    throw TypeError('cannot encode number outside of javascript safe integer range')
+  else if (num < 0)
     encodeNegative(num, buf)
   else
     encodePositive(num, buf)
@@ -15,44 +16,48 @@ const encode = exports.encode = (num, buf) => {
 
 const encodePositive = (num, buf) => {
   buf[0] = 0x80
-  for (var i = buf.length - 2; i > 0; i--) {
-    if (num === 0)
-      buf[i] = 0
-    else {
-      buf[i] = num % 0x100
-      num = Math.floor(num / 0x100)
-    }
+
+  for (var i = buf.length; i > 1; i--) {
+    buf[i-1] = num & 0xff
+    num = Math.floor(num / 0x100)
   }
 }
 
 const encodeNegative = (num, buf) => {
   buf[0] = 0xff
   var flipped = false
   num = num * -1
-  for (var i = buf.length - 2; i > 0; i--) {
-    var byte
-    if (num === 0)
-      byte = 0
-    else {
-      byte = num % 0x100
-      num = Math.floor(num / 0x100)
-    }
+  for (var i = buf.length; i > 1; i--) {
+    var byte = num & 0xff
+    num = Math.floor(num / 0x100)
     if (flipped)
-      buf[i] = onesComp(byte)
+      buf[i-1] = onesComp(byte)
     else if (byte === 0)
-      buf[i] = 0
+      buf[i-1] = 0
     else {
       flipped = true
-      buf[i] = twosComp(byte)
+      buf[i-1] = twosComp(byte)
     }
   }
 }
 
 const parse = exports.parse = (buf) => {
   var post = buf[buf.length - 1]
   var pre = buf[0]
-  return pre === 0x80 ? pos(buf.slice(1, buf.length - 1))
-   : twos(buf.slice(1, buf.length - 1))
+  var value;
+  if (pre === 0x80)
+    value = pos(buf.slice(1, buf.length))
+  else if (pre === 0xff)
+    value = twos(buf)
+  else
+    throw TypeError('invalid base256 encoding')
+
+  if (!Number.isSafeInteger(value))
+    // The number is so large that javascript cannot represent it with integer
+    // precision.
+    throw TypeError('parsed number outside of javascript javascript safe integer range')
+
+  return value
 }
 
 const twos = (buf) => {
@@ -71,9 +76,9 @@ const twos = (buf) => {
       f = twosComp(byte)
     }
     if (f !== 0)
-      sum += f * Math.pow(256, len - i - 1)
+      sum -= f * Math.pow(256, len - i - 1)
   }
-  return sum * -1
+  return sum
 }
 
 const pos = (buf) => {
diff --git a/test/large-numbers.js b/test/large-numbers.js
@@ -7,29 +7,56 @@ const t = require('tap')
 
 t.test('parse', t => {
   const cases = new Map([
-    ['ffffffffffffffffffffff20', -1],
-    ['800000000000100000000020', 68719476736],
-    ['fffffffffffffffe1ecc8020', -31536000],
-    ['fffffffffffffff000000020', -268435456],
-    ['800000010203040506070020', 72623859790382850],
-    ['ffffffffffffffffffffff00', -1],
-    ['800000000000100000000000', 68719476736],
-    ['fffffffffffffffe1ecc8000', -31536000],
-    ['fffffffffffffff000000000', -268435456],
-    ['800000010203040506070000', 72623859790382850]
+    ['ffffffffffffffffffffffff', -1],
+    ['800000000000100000000020', 17592186044448],
+    ['fffffffffffffffe1ecc8020', -8073215968],
+    ['fffffffffffffff000000020', -68719476704],
+    ['80000000001fffffffffffff', 9007199254740991],  // MAX_SAFE_INTEGER
+    ['ffffffffffe0000000000001', -9007199254740991], // MIN_SAFE_INTEGER
+    ['800000000000100000000000', 17592186044416],
+    ['fffffffffffffffe1ecc8000', -8073216000],
+    ['fffffffffffffff000000000', -68719476736],
+    ['800000000000000353b66200', 14289363456]
   ])
   t.plan(cases.size)
   cases.forEach((value, hex) =>
     t.equal(parse(Buffer.from(hex, 'hex')), value))
 })
 
+t.test('parse out of range', t => {
+  const cases = [
+    '800000030000000000000000',
+    '800000000020000000000000',  // MAX_SAFE_INTEGER + 1
+    'ffffffffffe0000000000000', // MIN_SAFE_INTEGER - 1
+    'fffffffffdd0000000000000',
+  ]
+  t.plan(cases.length)
+  cases.forEach((hex) =>
+    t.throws(_ => parse(Buffer.from(hex, 'hex')),
+      TypeError('parsed number outside of javascript javascript safe integer range')))
+})
+
+t.test('parse invalid base256 encoding', t => {
+  const cases = [
+    '313233343536373131',       // octal encoded
+    '700000030000000000000000', // does not start with 0x80 or 0xff
+  ]
+  t.plan(cases.length)
+  cases.forEach((hex) =>
+    t.throws(_ => parse(Buffer.from(hex, 'hex')),
+      TypeError('invalid base256 encoding')))
+})
+
 t.test('encode', t => {
   const cases = new Map([
-    ['ffffffffffffffffffffff20', -1],
-    ['800000000000100000000020', 68719476736],
-    ['fffffffffffffffe1ecc8020', -31536000],
-    ['fffffffffffffff000000020', -268435456],
-    ['800000010203040506070020', 72623859790382850]
+    ['ffffffffffffffffffffffff', -1],
+    ['800000000000100000000020', 17592186044448],
+    ['800000000000100000000000', 17592186044416],
+    ['fffffffffffffffe1ecc8020', -8073215968],
+    ['fffffffffffffff000000020', -68719476704],
+    ['fffffffffffffff000000000', -68719476736],      // Allows us to test the case where there's a trailing 00
+    ['80000000001fffffffffffff', 9007199254740991],  // MAX_SAFE_INTEGER
+    ['ffffffffffe0000000000001', -9007199254740991] // MIN_SAFE_INTEGER
   ])
   t.plan(2)
   t.test('alloc', t => {
@@ -43,3 +70,18 @@ t.test('encode', t => {
       t.equal(encode(value, Buffer.allocUnsafe(12)).toString('hex'), hex))
   })
 })
+
+t.test('encode unsafe numbers', t => {
+  const cases = [
+    Number.MAX_VALUE,
+    Number.MAX_SAFE_INTEGER + 1,
+    Number.MIN_SAFE_INTEGER - 1,
+    Number.MIN_VALUE,
+  ]
+
+  t.plan(cases.length)
+  cases.forEach((value) =>
+    t.throws(_ => encode(value),
+      TypeError('cannot encode number outside of javascript safe integer range')))
+})
+
