APInt.cpp File Reference

#include "llvm/ADT/APInt.h"
#include "llvm/ADT/StringRef.h"
#include "llvm/ADT/SmallString.h"
#include "llvm/Support/MathExtras.h"
#include <cmath>
#include <limits>
#include <cstring>
#include <cstdlib>
#include <iostream>

Namespaces
namespace	anonymous_namespace{APInt.cpp}
Defines
#define	DEBUG_TYPE "apint"
#define	rot(x, k) (((x)<<(k)) \| ((x)>>(32-(k))))
#define	mix(a, b, c)
#define	final(a, b, c)
#define	COMPILE_TIME_ASSERT(cond) extern int CTAssert[(cond) ? 1 : -1]
Functions
static uint64_t *	getClearedMemory (unsigned numWords)
	A utility function for allocating memory, checking for allocation failures, and ensuring the contents are zeroed.
static uint64_t *	getMemory (unsigned numWords)
	A utility function for allocating memory and checking for allocation failure.
static unsigned	getDigit (char cdigit, uint8_t radix)
	A utility function that converts a character to a digit.
static bool	add_1 (uint64_t dest[], uint64_t x[], unsigned len, uint64_t y)
	add_1 - This function adds a single "digit" integer, y, to the multiple "digit" integer array, x[].
static bool	sub_1 (uint64_t x[], unsigned len, uint64_t y)
	sub_1 - This function subtracts a single "digit" (64-bit word), y, from the multi-digit integer array, x[], propagating the borrowed 1 value until no further borrowing is neeeded or it runs out of "digits" in x.
static bool	add (uint64_t dest, const uint64_t x, const uint64_t *y, unsigned len)
	add - This function adds the integer array x to the integer array Y and places the result in dest.
static bool	sub (uint64_t dest, const uint64_t x, const uint64_t *y, unsigned len)
	Subtracts the integer array y from the integer array x.
static uint64_t	mul_1 (uint64_t dest[], uint64_t x[], unsigned len, uint64_t y)
	Multiplies an integer array, x, by a uint64_t integer and places the result into dest.
static void	mul (uint64_t dest[], uint64_t x[], unsigned xlen, uint64_t y[], unsigned ylen)
	Multiplies integer array x by integer array y and stores the result into the integer array dest.
static uint32_t	hashword (const uint64_t *k64, size_t length)
static uint32_t	hashword8 (const uint64_t k64)
static unsigned	countLeadingOnes_64 (uint64_t V, unsigned skip)
static void	KnuthDiv (unsigned u, unsigned v, unsigned q, unsigned r, unsigned m, unsigned n)
	Implementation of Knuth's Algorithm D (Division of nonnegative integers) from "Art of Computer Programming, Volume 2", section 4.3.1, p.
	COMPILE_TIME_ASSERT (integerPartWidth%2==0)
static integerPart	anonymous_namespace{APInt.cpp}::lowBitMask (unsigned int bits)
static integerPart	anonymous_namespace{APInt.cpp}::lowHalf (integerPart part)
static integerPart	anonymous_namespace{APInt.cpp}::highHalf (integerPart part)
static unsigned int	anonymous_namespace{APInt.cpp}::partMSB (integerPart value)
static unsigned int	anonymous_namespace{APInt.cpp}::partLSB (integerPart value)

Define Documentation

#define COMPILE_TIME_ASSERT ( cond ) extern int CTAssert[(cond) ? 1 : -1]

#define DEBUG_TYPE "apint"

#define final	(	a,
		b,
		c	)

Value:

{ \
    c ^= b; c -= rot(b,14); \
    a ^= c; a -= rot(c,11); \
    b ^= a; b -= rot(a,25); \
    c ^= b; c -= rot(b,16); \
    a ^= c; a -= rot(c,4);  \
    b ^= a; b -= rot(a,14); \
    c ^= b; c -= rot(b,24); \
  }

#define mix	(	a,
		b,
		c	)

Value:

{ \
    a -= c;  a ^= rot(c, 4);  c += b; \
    b -= a;  b ^= rot(a, 6);  a += c; \
    c -= b;  c ^= rot(b, 8);  b += a; \
    a -= c;  a ^= rot(c,16);  c += b; \
    b -= a;  b ^= rot(a,19);  a += c; \
    c -= b;  c ^= rot(b, 4);  b += a; \
  }

#define rot	(	x,
		k		)	(((x)<<(k)) \| ((x)>>(32-(k))))

Function Documentation

static bool add	(	uint64_t *	dest,
		const uint64_t *	x,
		const uint64_t *	y,
		unsigned	len
	)			`[static]`

add - This function adds the integer array x to the integer array Y and places the result in dest.

Returns:: the carry out from the addition General addition of 64-bit integer arrays

static bool add_1	(	uint64_t	dest[],
		uint64_t	x[],
		unsigned	len,
		uint64_t	y
	)			`[static]`

add_1 - This function adds a single "digit" integer, y, to the multiple "digit" integer array, x[].

x[] is modified to reflect the addition and 1 is returned if there is a carry out, otherwise 0 is returned.

Returns:: the carry of the addition.

COMPILE_TIME_ASSERT ( integerPartWidth% 2 = =0 )

static unsigned countLeadingOnes_64	(	uint64_t	V,
		unsigned	skip
	)			`[static]`

static uint64_t* getClearedMemory ( unsigned numWords ) [inline, static]

A utility function for allocating memory, checking for allocation failures, and ensuring the contents are zeroed.

static unsigned getDigit	(	char	cdigit,
		uint8_t	radix
	)			`[inline, static]`

A utility function that converts a character to a digit.

static uint64_t* getMemory ( unsigned numWords ) [inline, static]

A utility function for allocating memory and checking for allocation failure.

The content is not zeroed.

static uint32_t hashword	(	const uint64_t *	k64,
		size_t	length
	)			`[inline, static]`

static uint32_t hashword8 ( const uint64_t k64 ) [inline, static]

static void KnuthDiv	(	unsigned *	u,
		unsigned *	v,
		unsigned *	q,
		unsigned *	r,
		unsigned	m,
		unsigned	n
	)			`[static]`

Implementation of Knuth's Algorithm D (Division of nonnegative integers) from "Art of Computer Programming, Volume 2", section 4.3.1, p.

272. The variables here have the same names as in the algorithm. Comments explain the algorithm and any deviation from it.

static void mul	(	uint64_t	dest[],
		uint64_t	x[],
		unsigned	xlen,
		uint64_t	y[],
		unsigned	ylen
	)			`[static]`

Multiplies integer array x by integer array y and stores the result into the integer array dest.

Note that dest's size must be >= xlen + ylen. Generalized multiplicate of integer arrays.

static uint64_t mul_1	(	uint64_t	dest[],
		uint64_t	x[],
		unsigned	len,
		uint64_t	y
	)			`[static]`

Multiplies an integer array, x, by a uint64_t integer and places the result into dest.

Returns:: the carry out of the multiplication. Multiply a multi-digit APInt by a single digit (64-bit) integer.

static bool sub	(	uint64_t *	dest,
		const uint64_t *	x,
		const uint64_t *	y,
		unsigned	len
	)			`[static]`

Subtracts the integer array y from the integer array x.

Returns:: returns the borrow out. Generalized subtraction of 64-bit integer arrays.

static bool sub_1	(	uint64_t	x[],
		unsigned	len,
		uint64_t	y
	)			`[static]`

sub_1 - This function subtracts a single "digit" (64-bit word), y, from the multi-digit integer array, x[], propagating the borrowed 1 value until no further borrowing is neeeded or it runs out of "digits" in x.

The result is 1 if "borrowing" exhausted the digits in x, or 0 if x was not exhausted. In other words, if y > x then this function returns 1, otherwise 0.

Returns:: the borrow out of the subtraction

APInt.cpp File Reference

Namespaces

Defines

Functions

Define Documentation

Function Documentation