Skip to main content
Module

x/web_bson/src/decimal128.ts

web_bson is a fork from mongodb/js-bson
Go to Latest
File
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854
import { BSONTypeError } from "./error.ts";import { Long } from "./long.ts";
const PARSE_STRING_REGEXP = /^(\+|-)?(\d+|(\d*\.\d*))?(E|e)?([-+])?(\d+)?$/;const PARSE_INF_REGEXP = /^(\+|-)?(Infinity|inf)$/i;const PARSE_NAN_REGEXP = /^(\+|-)?NaN$/i;
const EXPONENT_MAX = 6111;const EXPONENT_MIN = -6176;const EXPONENT_BIAS = 6176;const MAX_DIGITS = 34;
// Nan value bits as 32 bit values (due to lack of longs)const NAN_BUFFER = [ 0x7c, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,].reverse();// Infinity value bits 32 bit values (due to lack of longs)const INF_NEGATIVE_BUFFER = [ 0xf8, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,].reverse();const INF_POSITIVE_BUFFER = [ 0x78, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,].reverse();
const EXPONENT_REGEX = /^([-+])?(\d+)?$/;
// Extract least significant 5 bitsconst COMBINATION_MASK = 0x1f;// Extract least significant 14 bitsconst EXPONENT_MASK = 0x3fff;// Value of combination field for Infconst COMBINATION_INFINITY = 30;// Value of combination field for NaNconst COMBINATION_NAN = 31;
// Detect if the value is a digitfunction isDigit(value: string): boolean { return !isNaN(parseInt(value, 10));}
// Divide two uint128 valuesfunction divideu128(value: { parts: [number, number, number, number] }) { const DIVISOR = Long.fromNumber(1000 * 1000 * 1000); let _rem = Long.fromNumber(0);
if ( !value.parts[0] && !value.parts[1] && !value.parts[2] && !value.parts[3] ) { return { quotient: value, rem: _rem }; }
for (let i = 0; i <= 3; i++) { // Adjust remainder to match value of next dividend _rem = _rem.shiftLeft(32); // Add the divided to _rem _rem = _rem.add(new Long(value.parts[i], 0)); value.parts[i] = _rem.div(DIVISOR).low; _rem = _rem.modulo(DIVISOR); }
return { quotient: value, rem: _rem };}
// Multiply two Long values and return the 128 bit valuefunction multiply64x2(left: Long, right: Long): { high: Long; low: Long } { if (!left && !right) { return { high: Long.fromNumber(0), low: Long.fromNumber(0) }; }
const leftHigh = left.shiftRightUnsigned(32); const leftLow = new Long(left.getLowBits(), 0); const rightHigh = right.shiftRightUnsigned(32); const rightLow = new Long(right.getLowBits(), 0);
let productHigh = leftHigh.multiply(rightHigh); let productMid = leftHigh.multiply(rightLow); const productMid2 = leftLow.multiply(rightHigh); let productLow = leftLow.multiply(rightLow);
productHigh = productHigh.add(productMid.shiftRightUnsigned(32)); productMid = new Long(productMid.getLowBits(), 0) .add(productMid2) .add(productLow.shiftRightUnsigned(32));
productHigh = productHigh.add(productMid.shiftRightUnsigned(32)); productLow = productMid.shiftLeft(32).add( new Long(productLow.getLowBits(), 0), );
// Return the 128 bit result return { high: productHigh, low: productLow };}
function lessThan(left: Long, right: Long): boolean { // Make values unsigned const uhleft = left.high >>> 0; const uhright = right.high >>> 0;
// Compare high bits first if (uhleft < uhright) { return true; }
if (uhleft === uhright) { const ulleft = left.low >>> 0; const ulright = right.low >>> 0; if (ulleft < ulright) return true; }
return false;}
function invalidErr(string: string, message: string) { throw new BSONTypeError( `"${string}" is not a valid Decimal128 string - ${message}`, );}
export interface Decimal128Extended { $numberDecimal: string;}
/** * A class representation of the BSON Decimal128 type. * @public */export class Decimal128 { _bsontype = "Decimal128"; readonly bytes!: Uint8Array;
/** * @param bytes - a buffer containing the raw Decimal128 bytes in little endian order, * or a string representation as returned by .toString() */ constructor(bytes: Uint8Array | string) { this.bytes = typeof bytes === "string" ? Decimal128.fromString(bytes).bytes : bytes; }
/** * Create a Decimal128 instance from a string representation * * @param representation - a numeric string representation. */ static fromString(representation: string): Decimal128 { // Parse state tracking let isNegative = false; let sawRadix = false; let foundNonZero = false;
// Total number of significant digits (no leading or trailing zero) let significantDigits = 0; // Total number of significand digits read let nDigitsRead = 0; // Total number of digits (no leading zeros) let nDigits = 0; // The number of the digits after radix let radixPosition = 0; // The index of the first non-zero in *str* let firstNonZero = 0;
// Digits Array const digits = [0]; // The number of digits in digits let nDigitsStored = 0; // Insertion pointer for digits let digitsInsert = 0; // The index of the first non-zero digit let firstDigit = 0; // The index of the last digit let lastDigit = 0;
// Exponent let exponent = 0; // loop index over array let i = 0; // The high 17 digits of the significand let significandHigh = new Long(0, 0); // The low 17 digits of the significand let significandLow = new Long(0, 0); // The biased exponent let biasedExponent = 0;
// Read index let index = 0;
// Naively prevent against REDOS attacks. // TODO: implementing a custom parsing for this, or refactoring the regex would yield // further gains. if (representation.length >= 7000) { throw new BSONTypeError( `${representation} not a valid Decimal128 string`, ); }
// Results const stringMatch = representation.match(PARSE_STRING_REGEXP); const infMatch = representation.match(PARSE_INF_REGEXP); const nanMatch = representation.match(PARSE_NAN_REGEXP);
// Validate the string if ( (!stringMatch && !infMatch && !nanMatch) || representation.length === 0 ) { throw new BSONTypeError( `${representation} not a valid Decimal128 string`, ); }
if (stringMatch) { // full_match = stringMatch[0] // sign = stringMatch[1]
const unsignedNumber = stringMatch[2]; // stringMatch[3] is undefined if a whole number (ex "1", 12") // but defined if a number w/ decimal in it (ex "1.0, 12.2")
const e = stringMatch[4]; const expSign = stringMatch[5]; const expNumber = stringMatch[6];
// they provided e, but didn't give an exponent number. for ex "1e" if (e && expNumber === undefined) { invalidErr(representation, "missing exponent power"); }
// they provided e, but didn't give a number before it. for ex "e1" if (e && unsignedNumber === undefined) { invalidErr(representation, "missing exponent base"); }
if (e === undefined && (expSign || expNumber)) { invalidErr(representation, "missing e before exponent"); } }
// Get the negative or positive sign if (representation[index] === "+" || representation[index] === "-") { isNegative = representation[index++] === "-"; }
// Check if user passed Infinity or NaN if (!isDigit(representation[index]) && representation[index] !== ".") { if (representation[index] === "i" || representation[index] === "I") { return new Decimal128( new Uint8Array( isNegative ? INF_NEGATIVE_BUFFER : INF_POSITIVE_BUFFER, ), ); } if (representation[index] === "N") { return new Decimal128(new Uint8Array(NAN_BUFFER)); } }
// Read all the digits while (isDigit(representation[index]) || representation[index] === ".") { if (representation[index] === ".") { if (sawRadix) invalidErr(representation, "contains multiple periods");
sawRadix = true; index += 1; continue; }
if ( nDigitsStored < 34 && (representation[index] !== "0" || foundNonZero) ) { if (!foundNonZero) { firstNonZero = nDigitsRead; }
foundNonZero = true;
// Only store 34 digits digits[digitsInsert++] = parseInt(representation[index], 10); nDigitsStored += 1; }
if (foundNonZero) nDigits += 1; if (sawRadix) radixPosition += 1;
nDigitsRead += 1; index += 1; }
if (sawRadix && !nDigitsRead) { throw new BSONTypeError( `${representation} not a valid Decimal128 string`, ); }
// Read exponent if exists if (representation[index] === "e" || representation[index] === "E") { // Read exponent digits const match = representation.substr(++index).match(EXPONENT_REGEX);
// No digits read if (!match || !match[2]) { return new Decimal128(new Uint8Array(NAN_BUFFER)); }
// Get exponent exponent = parseInt(match[0], 10);
// Adjust the index index += match[0].length; }
// Return not a number if (representation[index]) { return new Decimal128(new Uint8Array(NAN_BUFFER)); }
// Done reading input // Find first non-zero digit in digits firstDigit = 0;
if (!nDigitsStored) { firstDigit = 0; lastDigit = 0; digits[0] = 0; nDigits = 1; nDigitsStored = 1; significantDigits = 0; } else { lastDigit = nDigitsStored - 1; significantDigits = nDigits; if (significantDigits !== 1) { while (digits[firstNonZero + significantDigits - 1] === 0) { significantDigits -= 1; } } }
// Normalization of exponent // Correct exponent based on radix position, and shift significand as needed // to represent user input
// Overflow prevention exponent = exponent <= radixPosition && radixPosition - exponent > 1 << 14 ? EXPONENT_MIN : exponent - radixPosition;
// Attempt to normalize the exponent while (exponent > EXPONENT_MAX) { // Shift exponent to significand and decrease lastDigit += 1;
if (lastDigit - firstDigit > MAX_DIGITS) { // Check if we have a zero then just hard clamp, otherwise fail const digitsString = digits.join(""); if (digitsString.match(/^0+$/)) { exponent = EXPONENT_MAX; break; }
invalidErr(representation, "overflow"); } exponent -= 1; }
while (exponent < EXPONENT_MIN || nDigitsStored < nDigits) { // Shift last digit. can only do this if < significant digits than # stored. if (lastDigit === 0 && significantDigits < nDigitsStored) { exponent = EXPONENT_MIN; significantDigits = 0; break; }
if (nDigitsStored < nDigits) { // adjust to match digits not stored nDigits -= 1; } else { // adjust to round lastDigit -= 1; }
if (exponent < EXPONENT_MAX) { exponent += 1; } else { // Check if we have a zero then just hard clamp, otherwise fail const digitsString = digits.join(""); if (digitsString.match(/^0+$/)) { exponent = EXPONENT_MAX; break; } invalidErr(representation, "overflow"); } }
// Round // We've normalized the exponent, but might still need to round. if (lastDigit - firstDigit + 1 < significantDigits) { let endOfString = nDigitsRead;
// If we have seen a radix point, 'string' is 1 longer than we have // documented with ndigits_read, so inc the position of the first nonzero // digit and the position that digits are read to. if (sawRadix) { firstNonZero += 1; endOfString += 1; } // if negative, we need to increment again to account for - sign at start. if (isNegative) { firstNonZero += 1; endOfString += 1; }
const roundDigit = parseInt( representation[firstNonZero + lastDigit + 1], 10, ); let roundBit = 0;
if (roundDigit >= 5) { roundBit = 1; if (roundDigit === 5) { roundBit = digits[lastDigit] % 2 === 1 ? 1 : 0; for (i = firstNonZero + lastDigit + 2; i < endOfString; i++) { if (parseInt(representation[i], 10)) { roundBit = 1; break; } } } }
if (roundBit) { let dIdx = lastDigit;
for (; dIdx >= 0; dIdx--) { if (++digits[dIdx] > 9) { digits[dIdx] = 0;
// overflowed most significant digit if (dIdx === 0) { if (exponent < EXPONENT_MAX) { exponent += 1; digits[dIdx] = 1; } else { return new Decimal128( new Uint8Array( isNegative ? INF_NEGATIVE_BUFFER : INF_POSITIVE_BUFFER, ), ); } } } } } }
// Encode significand // The high 17 digits of the significand significandHigh = Long.fromNumber(0); // The low 17 digits of the significand significandLow = Long.fromNumber(0);
// read a zero if (significantDigits === 0) { significandHigh = Long.fromNumber(0); significandLow = Long.fromNumber(0); } else if (lastDigit - firstDigit < 17) { let dIdx = firstDigit; significandLow = Long.fromNumber(digits[dIdx++]); significandHigh = new Long(0, 0);
for (; dIdx <= lastDigit; dIdx++) { significandLow = significandLow.multiply(Long.fromNumber(10)); significandLow = significandLow.add(Long.fromNumber(digits[dIdx])); } } else { let dIdx = firstDigit; significandHigh = Long.fromNumber(digits[dIdx++]);
for (; dIdx <= lastDigit - 17; dIdx++) { significandHigh = significandHigh.multiply(Long.fromNumber(10)); significandHigh = significandHigh.add(Long.fromNumber(digits[dIdx])); }
significandLow = Long.fromNumber(digits[dIdx++]);
for (; dIdx <= lastDigit; dIdx++) { significandLow = significandLow.multiply(Long.fromNumber(10)); significandLow = significandLow.add(Long.fromNumber(digits[dIdx])); } }
const significand = multiply64x2( significandHigh, Long.fromString("100000000000000000"), ); significand.low = significand.low.add(significandLow);
if (lessThan(significand.low, significandLow)) { significand.high = significand.high.add(Long.fromNumber(1)); }
// Biased exponent biasedExponent = exponent + EXPONENT_BIAS; const dec = { low: Long.fromNumber(0), high: Long.fromNumber(0) };
// Encode combination, exponent, and significand. if ( significand.high.shiftRightUnsigned(49).and(Long.fromNumber(1)).equals( Long.fromNumber(1), ) ) { // Encode '11' into bits 1 to 3 dec.high = dec.high.or(Long.fromNumber(0x3).shiftLeft(61)); dec.high = dec.high.or( Long.fromNumber(biasedExponent).and( Long.fromNumber(0x3f_ff).shiftLeft(47), ), ); dec.high = dec.high.or( significand.high.and(Long.fromNumber(0x7f_ff_ff_ff_ff_ff)), ); } else { dec.high = dec.high.or( Long.fromNumber(biasedExponent & 0x3f_ff).shiftLeft(49), ); dec.high = dec.high.or( significand.high.and(Long.fromNumber(0x1_ff_ff_ff_ff_ff_ff)), ); }
dec.low = significand.low;
// Encode sign if (isNegative) { dec.high = dec.high.or(Long.fromString("9223372036854775808")); }
// Encode into a buffer const buffer = new Uint8Array(16); index = 0;
// Encode the low 64 bits of the decimal // Encode low bits buffer[index++] = dec.low.low & 0xff; buffer[index++] = (dec.low.low >> 8) & 0xff; buffer[index++] = (dec.low.low >> 16) & 0xff; buffer[index++] = (dec.low.low >> 24) & 0xff; // Encode high bits buffer[index++] = dec.low.high & 0xff; buffer[index++] = (dec.low.high >> 8) & 0xff; buffer[index++] = (dec.low.high >> 16) & 0xff; buffer[index++] = (dec.low.high >> 24) & 0xff;
// Encode the high 64 bits of the decimal // Encode low bits buffer[index++] = dec.high.low & 0xff; buffer[index++] = (dec.high.low >> 8) & 0xff; buffer[index++] = (dec.high.low >> 16) & 0xff; buffer[index++] = (dec.high.low >> 24) & 0xff; // Encode high bits buffer[index++] = dec.high.high & 0xff; buffer[index++] = (dec.high.high >> 8) & 0xff; buffer[index++] = (dec.high.high >> 16) & 0xff; buffer[index++] = (dec.high.high >> 24) & 0xff;
// Return the new Decimal128 return new Decimal128(buffer); }
/** Create a string representation of the raw Decimal128 value */ toString(): string { // Note: bits in this routine are referred to starting at 0, // from the sign bit, towards the coefficient.
// decoded biased exponent (14 bits) let biasedExponent; // the number of significand digits let significandDigits = 0; // the base-10 digits in the significand const significand = new Array<number>(36); for (let i = 0; i < significand.length; i++) significand[i] = 0; // read pointer into significand let index = 0;
// true if the number is zero let isZero = false;
// the most significant significand bits (50-46) let significandMsb; // temporary storage for significand decoding let significand128: { parts: [number, number, number, number] } = { parts: [0, 0, 0, 0], }; // indexing variables let j; let k;
// Output string const string: string[] = [];
// Unpack index index = 0;
// Buffer reference const buffer = this.bytes;
// Unpack the low 64bits into a long // bits 96 - 127 const low = buffer[index++] | (buffer[index++] << 8) | (buffer[index++] << 16) | (buffer[index++] << 24); // bits 64 - 95 const midl = buffer[index++] | (buffer[index++] << 8) | (buffer[index++] << 16) | (buffer[index++] << 24);
// Unpack the high 64bits into a long // bits 32 - 63 const midh = buffer[index++] | (buffer[index++] << 8) | (buffer[index++] << 16) | (buffer[index++] << 24); // bits 0 - 31 const high = buffer[index++] | (buffer[index++] << 8) | (buffer[index++] << 16) | (buffer[index++] << 24);
// Unpack index index = 0;
// Create the state of the decimal const dec = { low: new Long(low, midl), high: new Long(midh, high), };
if (dec.high.lessThan(Long.ZERO)) { string.push("-"); }
// Decode combination field and exponent // bits 1 - 5 const combination = (high >> 26) & COMBINATION_MASK;
if (combination >> 3 === 3) { // Check for 'special' values if (combination === COMBINATION_INFINITY) { return `${string.join("")}Infinity`; } if (combination === COMBINATION_NAN) { return "NaN"; } biasedExponent = (high >> 15) & EXPONENT_MASK; significandMsb = 0x08 + ((high >> 14) & 0x01); } else { significandMsb = (high >> 14) & 0x07; biasedExponent = (high >> 17) & EXPONENT_MASK; }
// unbiased exponent const exponent = biasedExponent - EXPONENT_BIAS;
// Create string of significand digits
// Convert the 114-bit binary number represented by // (significand_high, significand_low) to at most 34 decimal // digits through modulo and division. significand128.parts[0] = (high & 0x3f_ff) + ((significandMsb & 0xf) << 14); significand128.parts[1] = midh; significand128.parts[2] = midl; significand128.parts[3] = low;
if ( significand128.parts[0] === 0 && significand128.parts[1] === 0 && significand128.parts[2] === 0 && significand128.parts[3] === 0 ) { isZero = true; } else { for (k = 3; k >= 0; k--) { let leastDigits = 0; // Perform the divide const result = divideu128(significand128); significand128 = result.quotient; leastDigits = result.rem.low;
// We now have the 9 least significant digits (in base 2). // Convert and output to string. if (!leastDigits) continue;
for (j = 8; j >= 0; j--) { // significand[k * 9 + j] = Math.round(leastDigits % 10); significand[k * 9 + j] = leastDigits % 10; // leastDigits = Math.round(leastDigits / 10); leastDigits = Math.floor(leastDigits / 10); } } }
// Output format options: // Scientific - [-]d.dddE(+/-)dd or [-]dE(+/-)dd // Regular - ddd.ddd
if (isZero) { significandDigits = 1; significand[index] = 0; } else { significandDigits = 36; while (!significand[index]) { significandDigits -= 1; index += 1; } }
// the exponent if scientific notation is used const scientificExponent = significandDigits - 1 + exponent;
// The scientific exponent checks are dictated by the string conversion // specification and are somewhat arbitrary cutoffs. // // We must check exponent > 0, because if this is the case, the number // has trailing zeros. However, we *cannot* output these trailing zeros, // because doing so would change the precision of the value, and would // change stored data if the string converted number is round tripped. if ( scientificExponent >= 34 || scientificExponent <= -7 || exponent > 0 ) { // Scientific format
// if there are too many significant digits, we should just be treating numbers // as + or - 0 and using the non-scientific exponent (this is for the "invalid // representation should be treated as 0/-0" spec cases in decimal128-1.json) if (significandDigits > 34) { string.push(`${0}`); if (exponent > 0) string.push(`E+${exponent}`); else if (exponent < 0) string.push(`E${exponent}`); return string.join(""); }
string.push(`${significand[index++]}`); significandDigits -= 1;
if (significandDigits) { string.push("."); }
for (let i = 0; i < significandDigits; i++) { string.push(`${significand[index++]}`); }
// Exponent string.push("E"); if (scientificExponent > 0) { string.push(`+${scientificExponent}`); } else { string.push(`${scientificExponent}`); } } else { // Regular format with no decimal place if (exponent >= 0) { for (let i = 0; i < significandDigits; i++) { string.push(`${significand[index++]}`); } } else { let radixPosition = significandDigits + exponent;
// non-zero digits before radix if (radixPosition > 0) { for (let i = 0; i < radixPosition; i++) { string.push(`${significand[index++]}`); } } else { string.push("0"); }
string.push("."); // add leading zeros after radix while (radixPosition++ < 0) { string.push("0"); }
for ( let i = 0; i < significandDigits - Math.max(radixPosition - 1, 0); i++ ) { string.push(`${significand[index++]}`); } } }
return string.join(""); }
/** @internal */ toExtendedJSON(): Decimal128Extended { return { $numberDecimal: this.toString() }; }
/** @internal */ static fromExtendedJSON(doc: Decimal128Extended): Decimal128 { return Decimal128.fromString(doc.$numberDecimal); }
toJSON(): Decimal128Extended { return { $numberDecimal: this.toString() }; }
[Symbol.for("Deno.customInspect")](): string { return `new Decimal128("${this.toString()}")`; }}