File Coverage

n128.c

Criterion	Covered	Total	%
statement	243	244	99.5
branch	145	146	99.3
condition			n/a
subroutine			n/a
pod			n/a
total	388	390	99.4

/*
n128.c - 128-bit integer.

Copyright (C) 2012-2014 Tom Harrison
Original inet_pton4, inet_pton6 are Copyright (C) 2006 Free Software
Foundation.
Original interface, and the auth and ip_auth functions, are Copyright
(C) 1999-2002 RIPE NCC.

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License along
with this program; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
*/

#include
#include
#include
#include
#include

#include "n128.h"

#ifdef __cplusplus
extern "C" {
#endif

static char *power_strings[] = {
    "1",
    "2",
    "4",
    "8",
    "16",
    "32",
    "64",
    "128",
    "256",
    "512",
    "1024",
    "2048",
    "4096",
    "8192",
    "16384",
    "32768",
    "65536",
    "131072",
    "262144",
    "524288",
    "1048576",
    "2097152",
    "4194304",
    "8388608",
    "16777216",
    "33554432",
    "67108864",
    "134217728",
    "268435456",
    "536870912",
    "1073741824",
    "2147483648",
    "4294967296",
    "8589934592",
    "17179869184",
    "34359738368",
    "68719476736",
    "137438953472",
    "274877906944",
    "549755813888",
    "1099511627776",
    "2199023255552",
    "4398046511104",
    "8796093022208",
    "17592186044416",
    "35184372088832",
    "70368744177664",
    "140737488355328",
    "281474976710656",
    "562949953421312",
    "1125899906842624",
    "2251799813685248",
    "4503599627370496",
    "9007199254740992",
    "18014398509481984",
    "36028797018963968",
    "72057594037927936",
    "144115188075855872",
    "288230376151711744",
    "576460752303423488",
    "1152921504606846976",
    "2305843009213693952",
    "4611686018427387904",
    "9223372036854775808",
    "18446744073709551616",
    "36893488147419103232",
    "73786976294838206464",
    "147573952589676412928",
    "295147905179352825856",
    "590295810358705651712",
    "1180591620717411303424",
    "2361183241434822606848",
    "4722366482869645213696",
    "9444732965739290427392",
    "18889465931478580854784",
    "37778931862957161709568",
    "75557863725914323419136",
    "151115727451828646838272",
    "302231454903657293676544",
    "604462909807314587353088",
    "1208925819614629174706176",
    "2417851639229258349412352",
    "4835703278458516698824704",
    "9671406556917033397649408",
    "19342813113834066795298816",
    "38685626227668133590597632",
    "77371252455336267181195264",
    "154742504910672534362390528",
    "309485009821345068724781056",
    "618970019642690137449562112",
    "1237940039285380274899124224",
    "2475880078570760549798248448",
    "4951760157141521099596496896",
    "9903520314283042199192993792",
    "19807040628566084398385987584",
    "39614081257132168796771975168",
    "79228162514264337593543950336",
    "158456325028528675187087900672",
    "316912650057057350374175801344",
    "633825300114114700748351602688",
    "1267650600228229401496703205376",
    "2535301200456458802993406410752",
    "5070602400912917605986812821504",
    "10141204801825835211973625643008",
    "20282409603651670423947251286016",
    "40564819207303340847894502572032",
    "81129638414606681695789005144064",
    "162259276829213363391578010288128",
    "324518553658426726783156020576256",
    "649037107316853453566312041152512",
    "1298074214633706907132624082305024",
    "2596148429267413814265248164610048",
    "5192296858534827628530496329220096",
    "10384593717069655257060992658440192",
    "20769187434139310514121985316880384",
    "41538374868278621028243970633760768",
    "83076749736557242056487941267521536",
    "166153499473114484112975882535043072",
    "332306998946228968225951765070086144",
    "664613997892457936451903530140172288",
    "1329227995784915872903807060280344576",
    "2658455991569831745807614120560689152",
    "5316911983139663491615228241121378304",
    "10633823966279326983230456482242756608",
    "21267647932558653966460912964485513216",
    "42535295865117307932921825928971026432",
    "85070591730234615865843651857942052864",
    "170141183460469231731687303715884105728",
    "340282366920938463463374607431768211456",
};

/*
 * n128_set(): copy N128 value from other N128 value.
 * @dst: destination N128 object.
 * @src: source N128 object.
 */
void
n128_set(n128_t *dst, n128_t *src)
{
    memcpy(dst, src, sizeof(*dst));

    return;
}

/**
 * n128_set_ui(): set N128 value based on unsigned integer.
 * @n: the N128 object to be set.
 * @ui: the value to set.
 */
void
n128_set_ui(n128_t *n, unsigned int ui)
{
    n->nums[0] = 0;
    n->nums[1] = 0;
    n->nums[2] = 0;
    n->nums[3] = ui;

    return;
}

/**
 * n128_cmp_ui(): compare N128 value against unsigned integer.
 * @n: the N128 object.
 * @ui: unsigned integer.
 *
 * Returns 1 if @n is more than @ui, 0 if @n is equal to @ui and -1 if
 * @n is less than @ui.
 */
int
n128_cmp_ui(n128_t *n, unsigned int ui)
{
    return
        (n->nums[0] || n->nums[1] || n->nums[2] || (n->nums[3] > ui))
            ? 1
      : (n->nums[3] == ui)
            ? 0
            : -1;
}

/**
 * n128_blsft(): left-shift (circular) N128 value.
 * @n: the N128 object to shift.
 * @sft: the number of places by which the object should be shifted.
 */
void
n128_blsft(n128_t *n, int sft)
{
    n128_t copy;
    int i;
    uint32_t mask;
    int diff;

    diff = sft - 31;
    if (diff >= 0) {
        sft = 31;
    }

    for (i = 0; i < 4; ++i) {
        copy.nums[i] = n->nums[i];
    }
    for (i = 0; i < 4; ++i) {
        n->nums[i] <<= sft;
    }
    for (i = 0; i < 4; ++i) {
        mask = ((1 << sft) - 1) << (32 - sft);
        mask &= copy.nums[(i + 1) % 4];
        mask >>= (32 - sft);
        n->nums[i] |= mask;
    }

    if (diff >= 0) {
        n128_blsft(n, diff);
    }

    return;
}

/**
 * n128_brsft(): right-shift (circular) N128 value.
 * @n: the N128 object to shift.
 * @sft: the number of places by which the object should be shifted.
 */
void
n128_brsft(n128_t *n, int sft)
{
    n128_t copy;
    int i;
    uint32_t mask;
    int diff;

    diff = sft - 31;
    if (diff >= 0) {
        sft = 31;
    }

    for (i = 0; i < 4; ++i) {
        copy.nums[i] = n->nums[i];
    }
    for (i = 0; i < 4; ++i) {
        n->nums[i] >>= sft;
    }
    for (i = 0; i < 4; ++i) {
        mask = ((1 << sft) - 1);
        mask &= copy.nums[(i + 3) % 4];
        mask <<= (32 - sft);
        n->nums[i] |= mask;
    }

    if (diff >= 0) {
        n128_brsft(n, diff);
    }

    return;
}

/**
 * n128_and(): bitwise AND two N128 values.
 * @n1: first N128 object.
 * @n2: second N128 object.
 *
 * The result is stored in the first argument.
 */
void
n128_and(n128_t *n1, n128_t *n2)
{
    int i;

    for (i = 0; i < 4; i++) {
        n1->nums[i] &= n2->nums[i];
    }

    return;
}

/**
 * n128_ior(): bitwise OR two N128 values.
 * @n1: first N128 object.
 * @n2: second N128 object.
 *
 * The result is stored in the first argument.
 */
void
n128_ior(n128_t *n1, n128_t *n2)
{
    int i;

    for (i = 0; i < 4; i++) {
        n1->nums[i] |= n2->nums[i];
    }

    return;
}

/**
 * n128_xor(): bitwise XOR two N128 values.
 * @n1: first N128 object.
 * @n2: second N128 object.
 *
 * The result is stored in the first argument.
 */
void
n128_xor(n128_t *n1, n128_t *n2)
{
    int i;

    for (i = 0; i < 4; i++) {
        n1->nums[i] ^= n2->nums[i];
    }

    return;
}

/**
 * n128_add(): add two N128 values.
 * @n1: first N128 object.
 * @n2: second N128 object.
 *
 * The result is stored in the first argument. Overflow is as per
 * an unsigned integer.
 */
int
n128_add(n128_t *n1, n128_t *n2)
{
    int i;
    int j;

    for (i = 0; i < 4; i++) {
        n1->nums[i] += n2->nums[i];
    }
    for (i = 1; i < 4; i++) {
        j = i - 1;
        if (n1->nums[i] < n2->nums[i]) {
            n1->nums[j]++;
            while (n1->nums[j] == 0 && j--) {
                n1->nums[j]++;
            }
        }
    }

    return 1;
}

/**
 * n128_com(): take the complement of an N128 value.
 * @n: N128 object.
 *
 * The result is stored in the argument.
 */
void
n128_com(n128_t *n)
{
    int i;

    for (i = 0; i < 4; i++) {
        n->nums[i] = ~(n->nums[i]);
    }

    return;
}

/**
 * n128_add_ui(): add an unsigned integer value to an N128 value.
 * @n: N128 object.
 *
 * The result is stored in the first argument. Overflow is as per an
 * unsigned integer.
 */
int
n128_add_ui(n128_t *n, unsigned int ui)
{
    n128_t n2;
    n128_set_ui(&n2, ui);
    n128_add(n, &n2);

    return 1;
}

/**
 * n128_sub(): subtract an N128 value from another.
 * @n1: N128 object (minuend).
 * @n2: N128 object (subtrahend).
 *
 * The result is stored in the first argument. Overflow is not
 * handled: if @n2 is greater than @n1, the result will be zero.
 */
int
n128_sub(n128_t *n1, n128_t *n2)
{
    int res;
    n128_t n2c;
    n128_t *n2cp = &n2c;

    res = n128_cmp(n1, n2);
    if (res < 0) {
        return 0;
    }
    if (res == 0) {
        n128_set_ui(n1, 0);
        return 1;
    }
    n128_set(n2cp, n2);
    n128_com(n2cp);
    n128_add_ui(n2cp, 1);
    n128_add(n1, n2cp);

    return 1;
}

/**
 * n128_tstbit(): test whether a bit is set in an N128 value.
 * @n: N128 object.
 * @bit: the bit to test.
 *
 * Returns 1 if the bit is set, and zero if it is not. Bits begin at
 * zero and are ordered from least to most significant.
 */
int
n128_tstbit(n128_t *n, int bit)
{
    return (n->nums[3 - (bit / 32)] >> (bit % 32)) & 1;
}

/**
 * n128_setbit(): set a particular bit in an N128 value.
 * @n: N128 object.
 * @bit: the bit to set.
 *
 * See n128_tstbit().
 */
void
n128_setbit(n128_t *n, int bit)
{
    n->nums[3 - (bit / 32)] |= (1 << (bit % 32));
}

/**
 * n128_clrbit(): clear a particular bit in an N128 value.
 * @n: N128 object.
 * @bit: the bit to clear.
 *
 * See n128_tstbit().
 */
void
n128_clrbit(n128_t *n, int bit)
{
    n->nums[3 - (bit / 32)] &= ~(1 << (bit % 32));
}

/**
 * n128_cmp(): compare N128 value against another.
 * @n1: first N128 object.
 * @n2: second N128 object.
 *
 * Returns 1 if @n1 is more than @n2, 0 if @n1 is equal to @n2 and -1 if
 * @n1 is less than @n2.
 */
int
n128_cmp(n128_t *n1, n128_t *n2)
{
    return (n1->nums[0] > n2->nums[0]) ?  1
         : (n1->nums[0] < n2->nums[0]) ? -1
         : (n1->nums[1] > n2->nums[1]) ?  1
         : (n1->nums[1] < n2->nums[1]) ? -1
         : (n1->nums[2] > n2->nums[2]) ?  1
         : (n1->nums[2] < n2->nums[2]) ? -1
         : (n1->nums[3] > n2->nums[3]) ?  1
         : (n1->nums[3] < n2->nums[3]) ? -1
                                       : 0;
}

/**
 * n128_set_str_binary(): set N128 value based on bitstring.
 * @n: destination N128 object.
 * @bitstr: the bitstring.
 * @len: the length of the bitstring.
 *
 * The bitstring's bits must be ordered from most to
 * least significant. Any character in the bitstring that is not the
 * character '0' will be treated as the character '1'.
 */
void
n128_set_str_binary(n128_t *n, const char *bitstr, int len)
{
    int i;
    int j;
    int mylen;

    memset(n, 0, 4 * sizeof(uint32_t));
    mylen = (len > 128) ? 128 : len;

    if (mylen < 128) {
        for (i = 0; i < (128 - mylen); i++) {
            n128_clrbit(n, (127 - i));
        }
    } else {
        i = 0;
    }
    for (j = 0; i < 128; i++, j++) {
        if (bitstr[j] != '0') {
            n128_setbit(n, (127 - i));
        }
    }

    return;
}

static void
str_subtract(char *buf, int buflen, char *operand, int oplen)
{
    int i;
    int j;
    int carry = 0;
    int diff;

    for (i = buflen - 1, j = oplen - 1; i >= 0 && j >= 0; --i, --j) {
        diff = (buf[i] - (operand[j] + carry));
        if (diff >= 0) {
            buf[i] = diff + '0';
            carry = 0;
        } else {
            buf[i] = diff + '0' + 10;
            carry = 1;
        }
    }
    if (carry == 1) {
        buf[i]--;
    }

    return;
}

/**
 * n128_set_str_decimal(): set N128 value based on decimal string.
 * @n: destination N128 object.
 * @bitstr: the decimal string.
 * @len: the length of the decimal string.
 */
int
n128_set_str_decimal(n128_t *n, const char *str, int len)
{
    int i;
    char *ps;
    int ps_len;
    char buf[40];
    char *bufp;

    if (len > 39) {
        return 0;
    }

    bufp = buf;
    strncpy(bufp, str, len);
    buf[len] = '\0';
    n128_set_ui(n, 0);

    for (i = 0; i < len; i++) {
        if (!isdigit(str[i])) {
            return 0;
        }
    }

    if (power_strings[127][0] > str[0]) {
        return 0;
    }

    for (i = 127; i >= 0; i--) {
        if (!len) {
            break;
        }
        ps = power_strings[i];
        ps_len = strlen(ps);
        if (ps_len > len) {
            continue;
        } else {
            if (ps_len == len) {
                if (strcmp(bufp, ps) < 0) {
                    continue;
                }
            }
            str_subtract(bufp, len, ps, ps_len);
            while (*bufp == '0') {
                ++bufp;
                --len;
            }
            n128_setbit(n, i);
        }
    }
    if (len) {
        return 0;
    }

    return 1;
}

/**
 * n128_scan0(): return the index of the least significant cleared bit.
 * @n: N128 object.
 */
int
n128_scan0(n128_t *n)
{
    int i;

    for (i = 0; i < 128; i++) {
        if (!n128_tstbit(n, i)) {
            return i;
        }
    }

    return INT_MAX;
}

/**
 * n128_scan1(): return the index of the least significant set bit.
 * @n: N128 object.
 */
int
n128_scan1(n128_t *n)
{
    int i;

    for (i = 0; i < 128; i++) {
        if (n128_tstbit(n, i)) {
            return i;
        }
    }

    return INT_MAX;
}

/**
 * n128_rscan1(): return the index of the most significant set bit.
 * @n: N128 object.
 */
static int
n128_rscan1(n128_t *n)
{
    int i;

    for (i = 127; i >= 0; i--) {
        if (n128_tstbit(n, i)) {
            return i;
        }
    }

    return INT_MAX;
}

/**
 * n128_print_bin(): write an N128 value as a bitstring.
 * @n: N128 object.
 * @buf: bitstring buffer.
 * @ui_only: a boolean indicating whether only the first 32 bits
 * should be written.
 *
 * The buffer is null-terminated on completion, so it must have either
 * 129 or 33 characters' capacity, depending on the value of @ui_only.
 */
void
n128_print_bin(n128_t *n, char *buf, int ui_only)
{
    int i;
    int j;

    j = (ui_only) ? 0 : 3;

    for (; j >= 0; j--) {
        for (i = 31; i >= 0; i--) {
            *buf = (n128_tstbit(n, (j * 32) + i) ? '1' : '0');
            ++buf;
        }
    }
    *buf = '\0';

    return;
}

/**
 * n128_print_hex(): write an N128 value as a hexadecimal string.
 * @n: N128 object.
 * @buf: hexadecimal string buffer.
 *
 * The buffer is null-terminated on completion. It must have at least
 * 33 characters' capacity to handle all possible cases.
 */
void
n128_print_hex(n128_t *n, char *buf)
{
    int byte;
    int i;
    static const char *lookup = "0123456789abcdef";

    for (i = 0; i < 16; i++) {
        byte = (n->nums[i / 4] >> ((3 - (i % 4)) * 8)) & 0xFF;
        if (byte) {
            break;
        }
    }

    *buf++ = '0';
    *buf++ = 'x';

    if (i == 16) {
        *buf++ = '0';
    } else {
        for (; i < 16; i++) {
            byte = (n->nums[i / 4] >> ((3 - (i % 4)) * 8)) & 0xFF;
            *buf++ = lookup[(byte >> 4) & 0xF];
            *buf++ = lookup[byte & 0xF];
        }
    }

    *buf = '\0';

    return;
}

static int
n128_divmod_10(n128_t *n, n128_t *qp, n128_t *rp)
{
    n128_t ten;
    n128_t *tenp;
    n128_t t;
    n128_t *tp;
    n128_t na;
    n128_t *np;
    int shift;
    int shift1;
    int shift2;

    tenp = &ten;
    tp = &t;
    np = &na;
    n128_set(np, n);
    n128_set_ui(qp, 0);

    n128_set_ui(tenp, 10);
    shift1 = n128_rscan1(np);
    shift2 = n128_rscan1(tenp);
    shift = shift1 - shift2;
    if (shift < 0) {
        /* Divisor is larger than dividend. */
        n128_set_ui(qp, 0);
        n128_set(rp, np);
        return 1;
    }
    n128_blsft(tenp, shift);

    while (1) {
        n128_set(tp, np);
        if (n128_cmp(tp, tenp) >= 0) {
            n128_sub(tp, tenp);
            n128_setbit(qp, 0);
            n128_set(np, tp);
        }
        if (n128_cmp_ui(tenp, 10) == 0) {
            n128_set(rp, np);
            return 1;
        }
        n128_brsft(tenp, 1);
        n128_blsft(qp, 1);
    }
}

/**
 * n128_print_dec(): write an N128 value as a decimal string.
 * @n: N128 object.
 * @buf: decimal string buffer.
 *
 * The buffer is null-terminated on completion. It must have at least
 * 40 characters' capacity to handle all possible cases.
 */
void
n128_print_dec(n128_t *n, char *buf)
{
    int i = 0;
    int nums[50];
    int nc = 0;
    n128_t na;
    n128_t *np = &na;
    n128_t q;
    n128_t *qp = &q;
    n128_t r;
    n128_t *rp = &r;

    n128_set(np, n);
    n128_set(qp, np);

    if (n128_cmp_ui(qp, 0) == 0) {
        *buf++ = '0';
        *buf = '\0';
        return;
    }

    while (n128_cmp_ui(qp, 0) != 0) {
        n128_set(np, qp);
        n128_divmod_10(np, qp, rp);
        nums[nc++] = rp->nums[3];
    }

    --nc;
    for (i = nc; i >= 0; i--) {
        *buf++ = '0' + nums[i];
    }
    *buf = '\0';

    return;
}

#ifdef __cplusplus
}
#endif