From 8ad0040bbb42d7738965eea99e029145cce0b24e Mon Sep 17 00:00:00 2001 From: Bo Xu Date: Tue, 2 Dec 2014 13:06:22 -0800 Subject: Merge "Add big integer library"" This patch merges the 3 commits in master branch into one --- third_party/bigint/NumberlikeArray.hh | 184 ++++++++++++++++++++++++++++++++++ 1 file changed, 184 insertions(+) create mode 100644 third_party/bigint/NumberlikeArray.hh (limited to 'third_party/bigint/NumberlikeArray.hh') diff --git a/third_party/bigint/NumberlikeArray.hh b/third_party/bigint/NumberlikeArray.hh new file mode 100644 index 0000000000..f7917809f4 --- /dev/null +++ b/third_party/bigint/NumberlikeArray.hh @@ -0,0 +1,184 @@ +// Copyright 2014 PDFium Authors. All rights reserved. +// Use of this source code is governed by a BSD-style license that can be +// found in the LICENSE file. + +// Original code by Matt McCutchen, see the LICENSE file. + +#ifndef NUMBERLIKEARRAY_H +#define NUMBERLIKEARRAY_H + +#include // abort() +// Make sure we have NULL. +#ifndef NULL +#define NULL 0 +#endif + +/* A NumberlikeArray object holds a heap-allocated array of Blk with a + * length and a capacity and provides basic memory management features. + * BigUnsigned and BigUnsignedInABase both subclass it. + * + * NumberlikeArray provides no information hiding. Subclasses should use + * nonpublic inheritance and manually expose members as desired using + * declarations like this: + * + * public: + * NumberlikeArray< the-type-argument >::getLength; + */ +template +class NumberlikeArray { +public: + + // Type for the index of a block in the array + typedef unsigned int Index; + // The number of bits in a block, defined below. + static const unsigned int N; + + // The current allocated capacity of this NumberlikeArray (in blocks) + Index cap; + // The actual length of the value stored in this NumberlikeArray (in blocks) + Index len; + // Heap-allocated array of the blocks (can be NULL if len == 0) + Blk *blk; + + // Constructs a ``zero'' NumberlikeArray with the given capacity. + NumberlikeArray(Index c) : cap(c), len(0) { + blk = (cap > 0) ? (new Blk[cap]) : NULL; + } + + /* Constructs a zero NumberlikeArray without allocating a backing array. + * A subclass that doesn't know the needed capacity at initialization + * time can use this constructor and then overwrite blk without first + * deleting it. */ + NumberlikeArray() : cap(0), len(0) { + blk = NULL; + } + + // Destructor. Note that `delete NULL' is a no-op. + ~NumberlikeArray() { + delete [] blk; + } + + /* Ensures that the array has at least the requested capacity; may + * destroy the contents. */ + void allocate(Index c); + + /* Ensures that the array has at least the requested capacity; does not + * destroy the contents. */ + void allocateAndCopy(Index c); + + // Copy constructor + NumberlikeArray(const NumberlikeArray &x); + + // Assignment operator + void operator=(const NumberlikeArray &x); + + // Constructor that copies from a given array of blocks + NumberlikeArray(const Blk *b, Index blen); + + // ACCESSORS + Index getCapacity() const { return cap; } + Index getLength() const { return len; } + Blk getBlock(Index i) const { return blk[i]; } + bool isEmpty() const { return len == 0; } + + /* Equality comparison: checks if both objects have the same length and + * equal (==) array elements to that length. Subclasses may wish to + * override. */ + bool operator ==(const NumberlikeArray &x) const; + + bool operator !=(const NumberlikeArray &x) const { + return !operator ==(x); + } +}; + +/* BEGIN TEMPLATE DEFINITIONS. They are present here so that source files that + * include this header file can generate the necessary real definitions. */ + +template +const unsigned int NumberlikeArray::N = 8 * sizeof(Blk); + +template +void NumberlikeArray::allocate(Index c) { + // If the requested capacity is more than the current capacity... + if (c > cap) { + // Delete the old number array + delete [] blk; + // Allocate the new array + cap = c; + blk = new Blk[cap]; + } +} + +template +void NumberlikeArray::allocateAndCopy(Index c) { + // If the requested capacity is more than the current capacity... + if (c > cap) { + Blk *oldBlk = blk; + // Allocate the new number array + cap = c; + blk = new Blk[cap]; + // Copy number blocks + Index i; + for (i = 0; i < len; i++) + blk[i] = oldBlk[i]; + // Delete the old array + delete [] oldBlk; + } +} + +template +NumberlikeArray::NumberlikeArray(const NumberlikeArray &x) + : len(x.len) { + // Create array + cap = len; + blk = new Blk[cap]; + // Copy blocks + Index i; + for (i = 0; i < len; i++) + blk[i] = x.blk[i]; +} + +template +void NumberlikeArray::operator=(const NumberlikeArray &x) { + /* Calls like a = a have no effect; catch them before the aliasing + * causes a problem */ + if (this == &x) + return; + // Copy length + len = x.len; + // Expand array if necessary + allocate(len); + // Copy number blocks + Index i; + for (i = 0; i < len; i++) + blk[i] = x.blk[i]; +} + +template +NumberlikeArray::NumberlikeArray(const Blk *b, Index blen) + : cap(blen), len(blen) { + // Create array + blk = new Blk[cap]; + // Copy blocks + Index i; + for (i = 0; i < len; i++) + blk[i] = b[i]; +} + +template +bool NumberlikeArray::operator ==(const NumberlikeArray &x) const { + if (len != x.len) + // Definitely unequal. + return false; + else { + // Compare corresponding blocks one by one. + Index i; + for (i = 0; i < len; i++) + if (blk[i] != x.blk[i]) + return false; + // No blocks differed, so the objects are equal. + return true; + } +} + +#endif -- cgit v1.2.3