#include <limits.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <wchar.h>
#include <wctype.h>
#include "arith/integer.h"
#include "arith/peano.h"
#include "debug.h"
#include "memory/conspage.h"
#include "memory/consspaceobject.h"
#include "ops/equal.h"
#include "ops/lispops.h"

Include dependency graph for integer.c:

Macros
#define	_GNU_SOURCE

#define	SMALL_INT_LIMIT 24

Functions
struct cons_pointer	acquire_integer (int64_t value, struct cons_pointer more)
	Supply small valued integers from the small integer cache, if available.

struct cons_pointer	add_integers (struct cons_pointer a, struct cons_pointer b)
	Return a pointer to an integer representing the sum of the integers pointed to by `a` and `b`.

struct cons_pointer	append_cell (struct cons_pointer partial, struct cons_pointer digit)
	Return a copy of this `partial` with this `digit` appended.

struct cons_pointer	base_partial (int depth)

__int128_t	cell_value (struct cons_pointer c, char op, bool is_first_cell)
	Low level integer arithmetic, do not use elsewhere.

bool	equal_integer_integer (struct cons_pointer a, struct cons_pointer b)
	true if a and be are both integers whose value is the same value.

__int128_t	int128_to_integer (__int128_t val, struct cons_pointer less_significant, struct cons_pointer new)
	Overwrite the value field of the integer indicated by `new` with the least significant INTEGER_BITS bits of `val`, and return the more significant bits (if any) right-shifted by INTEGER_BITS places.

struct cons_pointer	integer_to_string (struct cons_pointer int_pointer, int base)
	return a string representation of this integer, which may be a bignum.

struct cons_pointer	integer_to_string_add_digit (int digit, int digits, struct cons_pointer tail)
	don't use; private to integer_to_string, and somewhat dodgy.

struct cons_pointer	make_integer (int64_t value, struct cons_pointer more)
	Allocate an integer cell representing this `value` and return a cons_pointer to it.

struct cons_pointer	multiply_integers (struct cons_pointer a, struct cons_pointer b)
	Return a pointer to an integer representing the product of the integers pointed to by `a` and `b`.

void	release_integer (struct cons_pointer p)
	if the value of p is less than the size of the small integer cache (and thus it was presumably supplied from there), suppress dec_ref.

Variables
const char *	hex_digits = "0123456789ABCDEF"
	hexadecimal digits for printing numbers.

struct cons_pointer	small_int_cache [SMALL_INT_LIMIT]

bool	small_int_cache_initialised = false

Macro Definition Documentation

◆ _GNU_SOURCE

#define _GNU_SOURCE

Definition at line 10 of file integer.c.

◆ SMALL_INT_LIMIT

#define SMALL_INT_LIMIT 24

Definition at line 50 of file integer.c.

Function Documentation

◆ acquire_integer()

struct cons_pointer acquire_integer	(	int64_t	value,
		struct cons_pointer	more
	)

Supply small valued integers from the small integer cache, if available.

The pattern here is intended to be that, at least within this file, instead of calling make_integer when an integer is required and dec_ref when it's no longer required, we call acquire_integer and release_integer respectively, in order to reduce allocation churn.

In the initial implementation, acquire_integer supplies the integer from the small integer cache if available, else calls make_integer. Later, more sophisticated caching of integers which are currently in play may be enabled.

Parameters

value	the value of the integer desired.
more	if this value is a bignum, the rest (less significant bits) of the value.

Returns: struct cons_pointer a pointer to the integer acquired.

Definition at line 129 of file integer.c.

References DEBUG_ALLOC, debug_print(), debug_printf(), make_integer(), NIL, nilp, pointer2cell, small_int_cache, small_int_cache_initialised, and SMALL_INT_LIMIT.

Referenced by add_integer_ratio(), add_integers(), base_partial(), multiply_integer_ratio(), multiply_integers(), multiply_ratio_ratio(), read_number(), and simplify_ratio().

◆ add_integers()

struct cons_pointer add_integers	(	struct cons_pointer	a,
		struct cons_pointer	b
	)

Return a pointer to an integer representing the sum of the integers pointed to by a and b.

If either isn't an integer, will return nil.

Definition at line 224 of file integer.c.

References acquire_integer(), cell_value(), DEBUG_ARITH, debug_dump_object(), debug_print(), debug_print_128bit(), debug_print_object(), debug_println(), int128_to_integer(), integerp, make_integer(), NIL, nilp, pointer2cell, and SMALL_INT_LIMIT.

Referenced by add_2(), add_ratio_ratio(), multiply_integers(), read_number(), and subtract_2().

◆ append_cell()

struct cons_pointer append_cell	(	struct cons_pointer	partial,
		struct cons_pointer	digit
	)

Return a copy of this partial with this digit appended.

Parameters

partial	the more significant bits of a possible bignum.
digit	the less significant bits of that possible bignum. NOTE: the name `digit` is technically correct but possibly misleading, because the numbering system here is base INT_CELL_BASE, currently x0fffffffffffffffL

Definition at line 308 of file integer.c.

References make_integer(), nilp, cons_space_object::payload, and pointer2cell.

Referenced by multiply_integers().

◆ base_partial()

struct cons_pointer base_partial ( int depth )

Definition at line 288 of file integer.c.

References acquire_integer(), DEBUG_ARITH, debug_printf(), and NIL.

Referenced by multiply_integers().

◆ cell_value()

__int128_t cell_value	(	struct cons_pointer	c,
		char	op,
		bool	is_first_cell
	)

Low level integer arithmetic, do not use elsewhere.

Parameters

c	a pointer to a cell, assumed to be an integer cell;
op	a character representing the operation: expected to be either '+' or '*'; behaviour with other values is undefined.
is_first_cell	true if this is the first cell in a bignum chain, else false.

See also: multiply_integers; add_integers

Definition at line 65 of file integer.c.

References DEBUG_ARITH, debug_print_128bit(), debug_printf(), debug_println(), INT_CELL_BASE, integerp, nilp, and pointer2cell.

Referenced by add_integers().

◆ equal_integer_integer()

bool equal_integer_integer	(	struct cons_pointer	a,
		struct cons_pointer	b
	)

true if a and be are both integers whose value is the same value.

Definition at line 511 of file integer.c.

References integerp, cons_space_object::payload, and pointer2cell.

Referenced by equal_integer_number(), and equal_ratio_ratio().

◆ int128_to_integer()

__int128_t int128_to_integer	(	__int128_t	val,
		struct cons_pointer	less_significant,
		struct cons_pointer	new
	)

Overwrite the value field of the integer indicated by new with the least significant INTEGER_BITS bits of val, and return the more significant bits (if any) right-shifted by INTEGER_BITS places.

Destructive, primitive, DO NOT USE in any context except primitive operations on integers. The value passed as new MUST be constructed with make_integer, NOT acquired with acquire_integer.

Parameters

val	the value to represent;
less_significant	the less significant words of this bignum, if any, else NIL;
new	a newly created integer, which will be destructively changed.

Returns: carry, if any, else 0.

Definition at line 193 of file integer.c.

References DEBUG_ARITH, debug_printf(), inc_ref(), INT_CELL_BASE, integerp, MAX_INTEGER, cons_space_object::payload, and pointer2cell.

Referenced by add_integers().

◆ integer_to_string()

struct cons_pointer integer_to_string	(	struct cons_pointer	int_pointer,
		int	base
	)

return a string representation of this integer, which may be a bignum.

The general principle of printing a bignum is that you print the least significant digit in whatever base you're dealing with, divide through by the base, print the next, and carry on until you've none left. Obviously, that means you print from right to left. Given that we build strings from right to left, 'printing' an integer to a lisp string would seem reasonably easy. The problem is when you jump from one integer object to the next. 64 bit integers don't align with decimal numbers, so when we get to the last digit from one integer cell, we have potentially to be looking to the next. H'mmmm.

Parameters

int_pointer	cons_pointer to the integer to print,
base	the base to print it in.

Definition at line 454 of file integer.c.

References c_string_to_lisp_string(), DEBUG_IO, debug_print(), debug_print_128bit(), debug_print_object(), debug_printf(), debug_println(), hex_digits, INT_CELL_BASE, integer_to_string_add_digit(), integerp, is_negative(), make_string(), MAX_INTEGER, NIL, nilp, cons_pointer::offset, pointer2cell, and stringp.

Referenced by print().

◆ integer_to_string_add_digit()

struct cons_pointer integer_to_string_add_digit	(	int	digit,
		int	digits,
		struct cons_pointer	tail
	)

don't use; private to integer_to_string, and somewhat dodgy.

Definition at line 420 of file integer.c.

References DEBUG_IO, debug_print_object(), debug_printf(), debug_println(), hex_digits, and make_string().

Referenced by integer_to_string().

◆ make_integer()

struct cons_pointer make_integer	(	int64_t	value,
		struct cons_pointer	more
	)

Allocate an integer cell representing this value and return a cons_pointer to it.

Parameters

value	an integer value;
more	`NIL`, or a pointer to the more significant cell(s) of this number. NOTE that if `more` is not `NIL`, `value` must not exceed `MAX_INTEGER`.

Definition at line 89 of file integer.c.

References allocate_cell(), DEBUG_ALLOC, debug_dump_object(), debug_print(), integerp, INTEGERTV, NIL, nilp, cons_space_object::payload, and pointer2cell.

Referenced by absolute(), acquire_integer(), add_integers(), add_meta_integer(), append_cell(), lisp_add(), lisp_divide(), lisp_get_hash(), lisp_length(), lisp_multiply(), negative(), and subtract_2().

◆ multiply_integers()

struct cons_pointer multiply_integers	(	struct cons_pointer	a,
		struct cons_pointer	b
	)

Return a pointer to an integer representing the product of the integers pointed to by a and b.

If either isn't an integer, will return nil.

Yes, this is one of Muhammad ibn Musa al-Khwarizmi's original recipes, so you'd think it would be easy; the reason that each step is documented is because I did not find it so.

Parameters