szigetij/biguint

Big unsigned integers (128, 256, 384, 512 or more bits), big (signed) integers and big decimal numbers.

(Not just) Big Unsigned Integers

But also Big Signed Integers and Big Decimal numbers.

C library providing fixed length integer types longer than 32/64 bits. The key design concepts of libbiguint are:

• Fast operations.
• Versatile function set.
• Supporting different hardware platforms.
• No dynamic memory handling.
• Only essential dependencies.
• Configurability and modularity.

All these make libbiguint suitable for embedded systems.

Features

BigUInt

libbiguint provides the following unsigned integer types:

• BigUInt128 (128 bits)
• BigUInt256 (256 bits)
• BigUInt384 (384 bits)
• BigUInt512 (512 bits)
• BigUInt<number> (1024 or even more bits)

All the provided types are accompanied by the following functions:

• addition and subtraction (add, sub, inc, dec, adc, sbc);
• multiplication and division (mul, dmul, div/mod);
• bit shift operations (shl, shr, rol, ror);
• bitwise operations (and, or, xor, not);
• bitwise manipulation (get, set, clr, overwrite);
• comparison (lt, eq, eqz);
• parsing and printing (from/to hex and dec strings);
• default and standard constructors (initializer functions).

The source code of type BigUInt128 is written in general manner. The source of all other biguint types are generated codes derived from BigUInt128. Types BigUInt256, BigUInt384, BigUInt512 and BigUInt<N> and adherent functions are optionally generated: the 256, 384 and 512 bit wide types are enabled by default, the N bit wide type is disabled. See configure --help for details.

BigInt

There are no explicit BigInt<number> types. We can store the signed big integers in BigUInt types. And most of the BigUInt functions work perfectly with BigInts. However, there are some functions which work differently for signed and unsigned integers, therefore they have their BigInt variants:

• parsing and printing (only dec strings);
• comparison (lt, ltz);
• division (div) and inversion (negate).

BigDecimal

Based on the corresponding BigUInt type, the following BigDecimal types are available:

• BigDecimal128
• BigDecimal256
• BigDecimal384
• BigDecimal512
• BigDecimal<number>

The functions accompanying these types are:

• addition and subtraction (add, sub);
• multiplication and division (mul, div, div_fast);
• precision adjustment;
• comparison (lt, eq);
• parsing and printing (only decimal format is supported).

All BigDecimal numbers are treated as signed values.

Installation

Get the source

Either clone the git source or download and extract the zip. Cloning git source is preferred. It is easier to update.

Autotools preparation

First, you need to run aclocal.

Next, run autoconf.

Finally, run automake --add-missing.

aclocal
autoconf
automake --add-missing

Configure & Install

The INSTALL file already describes how to run the configure script.

Installation prefix, compiler, target platform, etc. can be overridden at this step.

./configure
make
make install

Different configurations simultaneously

The configure script supports handling different build profiles simultaneously (see VPATH Builds). It generates the outputs (Makefiles) in the current working directory, whereever the configure script has been called. Executing make with these generated Makefiles will put the build output in the directory, where the Makefiles reside. Well, except for make install, of course.

You can create and manage multiple profiles, e.g., a Debug and a Release profile, within the base directory of the project:

mkdir -p dist/Debug
cd dist/Debug
../../configure CFLAGS="-O0 -g -W -Wall"
make
cd ../..

and

mkdir -p dist/Release
cd dist/Release
../../configure CFLAGS="-O2"
make
make install
cd ../..

Cross compilation is also supported. All you have to do is to create a profile for the desired target. Note, you have to give options --host and --build to configure, see the online manual.

How to use

Read some words about the naming conventions of functions here.

Use case #1: Summing very long values (C strings)

And getting the sum in C string (i.e., 0-terminated char array) as well.

#include <string.h>
#include "biguint128.h"

#define BUFLEN 42
int main() {
 const char a_str[]="123456789012345678901234567890";
 const char b_str[]="111111111111111111111111111111";
 char res_str[BUFLEN];

 BigUInt128 a = biguint128_ctor_deccstream(a_str, strlen(a_str));
 BigUInt128 b = biguint128_ctor_deccstream(b_str, strlen(b_str));

 BigUInt128 res = biguint128_add(&a, &b);
 res_str[biguint128_print_dec(&res, res_str, BUFLEN)]=0;
 // now res_str contains the sum of a and b in decimal format.
}

Use case #2: Multiplying beyond 64 bits

10^21 is greater than 2^64.

#include <stdio.h>
#include "biguint128.h"

int main() {
 BigUInt128 a = biguint128_value_of_uint(10000000);

 BigUInt128 asquare = biguint128_mul(&a,&a);
 BigUInt128 acube = biguint128_mul(&a,&asquare);

 printf("Highest bit set in a: %d\n", (int)biguint128_msb(&a));
 printf("Highest bit set in a^2: %d\n", (int)biguint128_msb(&asquare));
 printf("Highest bit set in a^3: %d\n", (int)biguint128_msb(&acube));

 return 0;
}

Examples

Check out the directory.

biguint's Issues

Pass-by-value functions

Create parameter-passed-by-value interface functions for BigUInt, BigInt and BigDecimal.
Currently, writing a y=a*x^2 + b*x + c evaluation is painful. It should be like

BigUint128 y = biguint128_addv(
 biguint128_addv(
  biguint128_mulv(a, biguint128_mulv(x,x)),
  biguint128_mulv(b, x)
 ),
 c
);

Here I used the v suffix for pass-by-value functions, but it can be other suffix.
List of functions that should have this parameter passed by value variant:

• add, sub, mul, div/mod;
• bitwise and, or, not, xor;
• shr, shl, ror, rol;
• eq, lt, eqz, ltz;
• print_dec, print_hex.

The bit manipulator functions, gbit, cbit, sbit, obit, msb, lzb, lzc do not need parameter passed-by-value variant.

Make release v1.2.0

Steps:

• Increase version number in configure.ac.
• Write some docs (Changelog).

Anything else?

Arithmetic without information loss

In add/sub functions we loose the carry bit, whereas mul drops the complete high half of the product.
Proposal:

• addc/subc with in/out carry bit parameter and
• mul2 returning pair of BigUIntxxx values.

Time to eliminate those codacy errors

Mostly complains about strlen.

Performance tests on other platforms

Before going deeper into performance analysis, and making fine code tuning according to performance tests results on intel i3 arch, do some performance tests on different platforms.

BigInt support (signed values)

What about two's complement very long integer support?
Most of the BigUInt functions can be used for them without any modification:

• add/sub/mul/div;
• bitwise operators.

What needs to be written:

• conversion from/to c_str;
• comparison (since f..fff is less than 0).

I would not introduce new type(s), just write some supplementary functions.

div10() function based on mul(x, inv(5))

Purpose

We have multiple solutions for division by 10. shr(div5(x),1) might be another candidate after the currently used div1000(mul100(x)) and div30(mul3(x)) solutions.
Benefit: if x is high, so that mul100(x) or even mul3(x) would overflow, the other candidates cannot be applied, whereas div5(x) does not have such limitations.
Maybe it is still slow, but let's check its performance.

Solution
If y=div5(x), then y == mul(x, inv(5)) in our case.
Why?
First, inv(5) always exists, as 4^n % 5 == (5-1)^n % 5 == (-1)^n, so for any BigUInt bit number we will find BigUInt<n> inv5 that fulfills the equation 5*inv5 == 1 (simplified). To be more precise, n is k * 8 * sizeof(UInt) / 2, so it is an even number, thus

• 4^(2*m) %5 == 1 =>
• (4^(2*m) - 1) %5 == 0 =>
• (4^(2*m) - 1) can be divided by 5 =>
• there is a certain z so that z * 5 == (4^(2*m) - 1) =>
• in our case z * 5 == -1 (simplified) =>
• (z * -1) * 5 == 1 =>
• (z * -1) is inv5.

We have to define inv5 in compile time as const or static variable, so we do not have to calculate it every time div5() function is called.

Next, we have to deal with the remainder. If mul(x,inv(5)) gives result in range [0,(-1 / 5)], the remainder is 0. Otherwise the remainder is either 1, 2, 3 or 4. Unfortunately, currently I do not know any efficient algorithm to determine value of the remainder.

Finally, div10() or div10_v5() can be written as

BigUIntTinyPair128 div10_v5(const BigUInt128 &a) {
 BigUIntTinyPair128 x = biguint128_div5(a);
 if (x.first &1) x.second += 5;
 biguint128_shr_tiny(&x.first, 1);
 return x;
}

Of course in case of signed values, we have to check the signedness..

Request for math functions with small values

Some operations, e.g., adding a single digit to a number or shifting a number by only some bits, can be performed faster than using the currently available functions.

Some suggestions:

• m10_ -- multiplication by 10 for internal usage (decimal parser);
• biguint128_shl_tiny, biguint128_shr_tiny -- shifting by less than UINT_BITS;
• biguint128_add_tiny -- adding UInt to BigUInt,
• etc.

Check performance of different x/10 implementations

We can realize x/10 as

• div(x,10),
• div1000(mul100(x)) or
• div30(mul3(x)).

Note that div30() and mul3() are not implemented yet.

The task is to create a performance test that compares these possibilities.
The test must be carried out on small, medium and large x values.

Support even bigger numbers

BigUInt256 and bigger types are generated (based on BigUInt128). The proposal is to take not only const values (e.g., 256, 512), but also values defined by the configure script.

Maybe, the list of target bitlengths should be a configuration variable defaulting to 256,386,512. Then during configuration it must be checked that each target bitlength

• is >128;
• can be divided by UInt bitlength;
• is unique in the list.

Improve div(x,y) performance

Seems like there is much to do:

• Once if the remainder gets 0, the internal conditional subtract & shift divisor cycle can be broken.
• If the remainder is gets very low, the divisor can be SHR-ed with more than 1 bit.
• If the original divisor is small and the dividend is large, the subtraction in the internal cycle does not affect the whole range of bits of the BigUInt type.
• Also as the internal remainder gets lower and lower, the lt(divisor, remainder) comparison could skip checking the high bits.

eqz, ltz functions

Nice to have functions:

• buint_bool biguint128_eqz(const BigUInt128 &a) (equals zero)
• buint_bool bigint128_ltz(const BigUInt128 &a) (less than zero / is negative)
• BigUInt128 bigint128_negate(const BigUInt128 &a) (*=-1 as interface function)
• BigUInt128 bigint128_value_of_uint(UInt a) (initialize with negative value)

request for better .prec setting / handling

In BigDecimalNNN, .prec handling is very rough.
First, bigdecimal128_ctor_prec can overflow even if prec gets decreased.
Next, gen_common_prec_ is used in comparisons (lt / eq), which relies on bigdecimal128_ctor_prec.
It is a problem that bigdecimal128_ctor_prec does not report whether overflow occured or not.

The goal of this task is to create a function that

• sets the precision just like bigdecimal128_ctor_prec;
• indicates somehow if there was overflow;
• in case of decreasing prec, works without any overflow possibility.

Request for floor() and ceil() functions

Some requirements:

• should work with positive and negative values;
• should preserve precision;
• should accept a precision parameter;
• make _assign variant as well.

Performance tests on shift operations

Write performance tests on shift operations:

• shl
• shl_or (with / without resetting dest before the operation)
• shr
• shr_assign (with / without resetting a between operations)
• ror
• rol

Support of inc/dec functions

Better call the inc(a) or dec(a) function, than add(a,1) or sub(a,1).
The declaration can be

BigUInt128 *biguint128_inc(BigUInt128 *a);
BigUInt128 *biguint128_dec(BigUInt128 *a);

make a safe variant of bigdecimal128_lt!

In bigdecimal128_lt overflow can happen. In case of overflow, the comparison does not work correctly.
The goal of this issue is to create a new function, bigdecimal128_lt_safe, so that

• it minimizes the risk of overflow;
• or even minimizes the number of biguint divisions (or multiplications);
• notifies the caller if the result of the comparison is not reliable doe to overflow.

The prototype of the function can be

buint_bool bigdecimal128_lt_safe(buint_bool *result, const BigDecimal128 *a, const BigDecimal128 *b);

build without 256,384,512 bitlength

For quick build 256/384 and 512 bitlength are not required.
Default: these lengths are enabled. To disable them do configure with
--without-biguint256 etc.

Request for multiplicative inverse function

input: merely a BigUInt value (as reference);
output: pair of BigUInt values, containing quotient and remainder.

Given input a, with result q (0<q), m, the following equation must be true:

a * q + m == max + 1

Request for a function that breaks a decimal value into integer and fractional parts

It seems to have more sense than floor() and ceil(), since these can be easily derived from this function.
It should be called trunc or break.
The prototype of the function can be

BigDecimal128 bigdecimal128_trunc(const BigDecimal128 *a, BigDecimal128 *frac);
// or
BigUIntPair128 bigdecimal128_trunc(const BigDecimal128 *a); // here the frac (.second of return value) inherits the precision of *a

Do not install example and performance test binaries

currently, they get installed. This is wrong.

Make bigdecimal add/sub safe!

If the difference between a.prec and b.prec is too large, add/sub operations will fail.
Currently, in bigdecimal128_add(), the caller is not notified about this failure.

Create functions

buint_bool bigdecimal128_add_safe(BigDecimal128 *dest, const BigDecimal128 *a, const BigDecimal128 *b);
buint_bool bigdecimal128_sub_safe(BigDecimal128 *dest, const BigDecimal128 *a, const BigDecimal128 *b);

Bigdecimal print error when output buffer is too short

If the decimal number with precision does not fit into the output buffer, the function should return 0.

char *buf[250];
char tin[]="10000000000000.0000000000001";
BigDecimal128 a = bigdecimal128_ctor_cstream(tin,28);
buint_size_t len = bigdecimal128_print(&a, buf, 26);

len is 15.

Expected behavior
len must be 0.

Move msb performance test to master branch

Split the commit containing msb_perf128.c and msb performance enhancement in uint.h/uint.c.
The changes in uint_msb can stay in branch PERFORMANCE_EXP, but the file tests/performance/msb_perc128.c should go to branch master.

Below 100% code coverage

if (msb_a < msb_b) {
 retv.second = biguint128_ctor_copy(a);
} else {

is not covered in biguint128_div.

put uint functions to uint.h as static inline

The uint functions call seem to be a big bottleneck.
Check the performance improvement after making these functions static inline.

compilation fails if USE_STD_TYPES is disabled

../../../../tests/performance/add_uperf.c: In function ‘exec_uint_test_’:
../../../../tests/performance/add_uperf.c:60:2: error: unknown type name ‘uint32_t’; did you mean ‘u_int32_t’?
   60 |  uint32_t loop_cnt;
      |  ^~~~~~~~
      |  u_int32_t
../../../../tests/performance/add_uperf.c:62:21: error: ‘false’ undeclared (first use in this function); did you mean ‘fclose’?
   62 |  buint_bool carry = false;
      |                     ^~~~~
      |                     fclose

Question: Can variables be rotated to left/right directly?

Like this

#define ROL(x, a)((((x) << (a)) | ((x) >> (256 - (a)))))
#define ROR(x, a)((((x) >> (a)) | ((x) << (256 - (a)))))

BigUInt256 var1
BigUInt256 var2
var1 = ROR(var1, 199);
var2 b = ROL(var2, 225);

make bigdecimal mul/div safe!

Almost done with bigdecimal ~_safe functions.
The missing ones are:

buint_bool bigdecimal128_mul_safe(BigDecimal128 *dest, const BigDecimal128 *a, const BigDecimal128 *b);
buint_bool bigdecimal128_div_safe(BigDecimal128 *dest, const BigDecimal128 *a, const BigDecimal128 *b, UInt prec);

The multiplication should be based on biguint128_dmul(), and result.second must be checked: it should be either all-zero or all-one (for negative values). Otherwise the multiplication fails.

The division should be a variant of bigdecimal128_div, where retv.val must be checked before

retv.val = biguint128_mul10(&retv.val);

and if multiplication overflow happens, the division fails.

make bigdecimal128_eq safe!

bigdecimal128_eq should be as safe as bigdecimal128_lt.

unit testing

full line / branch coverage must be reached

Request for fast biguint / uint division

The prototype of the functions should be

BigUIntTinyPair128 biguint128_div_uint(const BigUInt128 *a, UInt b);

The basic idea is the same how we divide a long decimal number with a single digit divisor:

12345 / 5:

a=12345;
b=5;
a = a0 + 10*a1 + 100*a2 + 1000*a3 + 10000*a4;
a4=1, a3=2, a2=3, a1=4, a0=5;

p4 = a4 = 1; p4/b = 1/5: d4=0, m4=1;
p3 = 10*m4 + a3 = 12; p3/b = 12 / 5: d3=2, m3=2;
p2 = 10*m3 + a2 = 23; p2/b = 23 / 5: d2=4, m2=3;
p1 = 10*m2 + a1 = 34; p1/b = 34 / 5: d1=6, m1=4;
p0 = 10*m1 + a0 = 45; p0/b = 45 / 5: d0=9, m0=0;

d = d0 + 10*d1 + 100*d2 + 1000*d3 + 10000*d4 = 2469
m = m0 = 0

This works for for BigUInt types as long as the architecture and the compiler supports double UInt division, e.g., UInt is uint32_t and uint64_t division is supported. Otherwise we have to spit b into HI(b) and LO(b) and the solution becomes somewhat more complicated:

a = 12345;
b = 42;

b = 10*bhi + blo;
bhi=4, blo=2;
bhix=bhi + (blo!=0) = 5;
blox= blo==0?0:10-blo = 8;

// split#1:
p: 1(0000), r: 2345
p/bhix=0;

// split#2:
p: 12(000), r: 345
p/bhix: d=2(00), m=2(000);

r + m + blox*d
 345
2000
1600
------
3945

// split#3:
p: 3(000), r: 945
p/bhix = 0;

// split#4:
p: 39, r: 45
p/bhix: d=7(0), m=4(00)

r + m + blox*d
  45
 400
 560
----
1005

// split#5:
p:10(00), r: 5
p/bhix: d=2(0), m=0

r + m + blox*d
   5
   0
 160
----
 165

// split#6:
// split#7:
p: 16(0), r: 5
p/bhix: d=3, m=1(0)

r + m + blox*d
  5
 10
 24
---
 39

===
d=2(00) + 7(0) + 2(0) + 3 = 293
m=39

Question: Can variables be XORed directly when using biguint?

Like this:

BigUInt256 var1 = 0xf5109583c8c61e884a22ed50fd579ac519ca46829d7f4c03aee883a02f6e0793;
BigUInt256 var2 = 0xc96ed6f80c1a691d0373772e531d5ee4aaeca263f4901423b27177e5f18dd2cf;

var1 ^= var2;

biguint128_print_dec writes garbage

If the buffer is shorter than required, biguint128_print_dec puts garbage into it (sometimes).

how to reproduce

parse a number, e.g., 256 and then print it into a buffer with length 2.

 BigUInt128 a = biguint128_ctor_deccstream("256", 3);
 buint_size_t len = biguint128_print_dec(&a, buffer, 2);

expected behavior

len: 0
buffer -- actually we do not care about buffer[0] and buffer[1] as long as len == 0.

actual behavior

len: 2
buffer: "56"

Docs about function naming

Write some words about the function naming concepts, about the suffices

• _assign
• _tiny
• _replace
• _brange
• _crange
• no suffix
• etc.

negative bigint division error

Describe the bug
biguint128_div does not work correctly for negative signed numbers (BigInt128)

To Reproduce

• biguint128_div with -100, 10 returns 36692093846346337460743176821135
• biguint128_div with -100, -10 returns 0
• biguint128_div with 100, -10 returns 0

Expected behavior

• biguint128_div with -100, 10 should return -10
• biguint128_div with -100, -10 should return 10
• biguint128_div with 100, -10 should return -10

and the remainder should be everywhere 0.

Environment:
all

request for abs() function

Create abs() and abs_assign() and also indicate somehow if the argument has been inverted, e.g.,

BigUInt128 *bigint128_abs_assign(BigUInt128 *a, buint_bool *result_inv);

Allow result_inv to be NULL.

Functions with input check

Create new function adapters with _safe suffix for functions like

• division - to avoid division by zero
• shift left/right
• etc.

Unify performance test executable names

Describe the bug
Currently there is a mess:

dist/Release$ ls tests/performance/
add_perf            div1000_512_perf.c  div10_256_perf.o  Makefile          print_256_perf.c
add_perf.o          div1000_512_perf.o  div10_512_perf    parse_perf        print_256_perf.o
div1000_256_perf    div1000_perf        div10_512_perf.c  parse_perf.o      print_perf
div1000_256_perf.c  div1000_perf.o      div10_512_perf.o  perf_common256.h  print_perf.o
div1000_256_perf.o  div10_256_perf      div10_perf        perf_common512.h  uint_perf
div1000_512_perf    div10_256_perf.c    div10_perf.o      print_256_perf    uint_perf.o

Expected format

• BigUInt executables: <something>_perf<bits>, and <bits> should be given even in case of BigUInt128
• BigDecimal executables: <something>_dperf<bits>
• UInt executables: <something>_uperf

Request for new, msb-related functions

First, biguint128_msb returns zero for biguint 1 and for 0 as well, although 0 occupies 0 bits, whereas 1 occupies 1 bit.
Also, in many cases we immediately convert the result of msb into cell index.

Proposal:

• new function (BigUint -> buint_size_t) that determines x for a so that x is the lowest possible number satisfying the condition that in bit range [x, BIGUINT_BITS) a does not have any bit set to 1.
• another new function (BigUint -> buint_size_t) that determines x for a so that x is the lowest possible number satisfying the condition that in cell range [x, BIGUINT_CELLS) all the cells of a equal to 0.

The name of these functions should refer to something like ``lowest clear/zero bit/cell''

Problem with uint64_t as UInt

First, 1 << a will fail, if 32<=a.
(1 is int by default.)
Explicit type conversion, i.e., (UInt)1 is required everywhere in such cases.

Furthermore, test files compile with warnings: %u vs. %llu must be clarified in printf() functions.
Tests written for 32 bit UInt must be skipped (and new tests must be introduced for 64 bit UInt).

BigDecimal

Create interface and implementation of BigDecimal types.
Internally, the BigDecimal should rely on a BigUInt and a non-negative (e.g., UInt) precision value.
The interface must include the following functions:

• basic arithmetics (add, sub, mul, div);
• comparison (less, equals);
• I/O (parse/print);
• precision adjustment.

Also, provide tests.
Finally, update the docs.

Circular shift functions

The ROL and ROR functions are easy to implement base on the current library functions. Maybe it is worth putting them into the library.
To tell the truth, after some performance enhancement experiments, I am not sure we need any native code instead of

// just kind of pseudo-code
buint buint_rol(buint a, size_t b) {
 buint hi = buint_shl(a, b);
 buint lo = buint_shr(a, BUINT_BITS-b);
 return buint_or(hi, lo);
}
buint buint_ror(buint a, size_t b) {
 return buint_rol(a, BUINT_BITS-b);
}

base storage type should be configurable

Is your feature request related to a problem? Please describe.
Whenever the host code has its own 128 bit unsigned type and I want to convert it into BigUInt128

• either I have to check the size of UInt;
• or char array itermediate type must be used.

Describe the solution you'd like
It would be nice to have uint32_t (stdint.h) instead of UInt.
More flexible solution would be a configurable type (along with configurable header with the typedef).

Describe alternatives you've considered
Byte array constructor and byte array export function - these could be simple memcpy()s in case of little-endian architectures.

set version to 1.3.0

As last issue to merge into master before the release of v1.3.0,
do the updates to

• autoconf.ac and
• ChangeLog

interface doc

Interface should be documented in doxygen style