diff options
| -rw-r--r-- | src/util/bits.c | 327 | ||||
| -rw-r--r-- | src/util/bits.h | 60 | ||||
| -rw-r--r-- | test/src/util/test_bits.c | 346 |
3 files changed, 733 insertions, 0 deletions
diff --git a/src/util/bits.c b/src/util/bits.c index 2e2faa2..21cf43e 100644 --- a/src/util/bits.c +++ b/src/util/bits.c @@ -1,2 +1,329 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017 J08nY + */ +#include <gen/types.h> #include "bits.h" +#include "util/memory.h" + +bits_t *bits_new(size_t bit_len) { + bits_t *result = try_calloc(sizeof(bits_t)); + size_t byte_len = BYTE_LEN(bit_len); + result->bits = try_calloc(byte_len); + result->allocated = byte_len; + result->bitlen = bit_len; + return result; +} + +bits_t *bits_copy(const bits_t *bits) { + bits_t *result = try_calloc(sizeof(bits_t)); + result->bitlen = bits->bitlen; + result->allocated = bits->allocated; + if (bits->allocated != 0) + result->bits = try_memdup(bits->bits, result->allocated); + return result; +} + +void bits_free(bits_t **bits) { + if (*bits) { + if ((*bits)->bits) { + try_free((*bits)->bits); + } + try_free(*bits); + *bits = NULL; + } +} + +bits_t *bits_from_i(GEN i) { + pari_sp ltop = avma; + GEN bitvec = binary_zv(i); + size_t bit_len = (size_t)glength(bitvec); + bits_t *result = bits_new(bit_len); + for (size_t j = 0; j < bit_len; ++j) { + if (gel(bitvec, j + 1) == (GEN)1) { + result->bits[j / 8] |= 1 << (7 - (j % 8)); + } + } + avma = ltop; + return result; +} + +bits_t *bits_from_hex(const char *hex_str) { + size_t nibble_len = strlen(hex_str); + bits_t *result = bits_new(nibble_len * 4); + for (size_t i = 0; i < nibble_len; ++i) { + char hex = hex_str[i]; + char nibble = 0; + if ('0' <= hex && hex <= '9') { + nibble = (char)(hex - '0'); + } else if ('a' <= hex && hex <= 'f') { + nibble = (char)(hex - 'a' + 10); + } else if ('A' <= hex && hex <= 'F') { + nibble = (char)(hex - 'A' + 10); + } + result->bits[i / 2] |= (nibble << (1 - (i % 2)) * 4); + } + return result; +} + +bits_t *bits_from_bin(const char *bin_str) { + size_t bit_len = strlen(bin_str); + bits_t *result = bits_new(bit_len); + for (size_t i = 0; i < bit_len; ++i) { + if (bin_str[i] == '1') { + result->bits[i / 8] |= 1 << (7 - (i % 8)); + } + } + return result; +} + +bits_t *bits_from_raw(const unsigned char *bits, size_t bit_len) { + bits_t *result = try_calloc(sizeof(bits_t)); + result->bitlen = bit_len; + result->allocated = BYTE_LEN(bit_len); + result->bits = try_memdup(bits, result->allocated); + return result; +} + +bits_t *bits_from_bitvec(GEN v) { + size_t bit_len = (size_t)glength(v); + bits_t *result = bits_new(bit_len); + for (size_t i = 0; i < bit_len; ++i) { + if (gel(v, i + 1) == (GEN)1) + result->bits[i / 8] |= 1 << (7 - (i % 8)); + } + return result; +} + +GEN bits_to_i(const bits_t *bits) { + pari_sp ltop = avma; + GEN result = stoi(0); + for (size_t i = 0; i < bits->bitlen; ++i) { + if (GET_BIT(bits->bits, i) != 0) + result = addii(result, int2n(bits->bitlen - i - 1)); + } + return gerepileupto(ltop, result); +} + +char *bits_to_hex(const bits_t *bits) { + char *result = try_calloc(BYTE_LEN(bits->bitlen) * 2 + 1); + //probably right pad with zeroes, as thats what is actually stored. + for (size_t i = 0; i < BYTE_LEN(bits->bitlen); ++i) { + sprintf(result + (i * 2), "%x", bits->bits[i]); + } + return result; +} + +char *bits_to_bin(const bits_t *bits) { + char *result = try_calloc(bits->bitlen + 1); + for (size_t i = 0; i < bits->bitlen; ++i) { + sprintf(result + i, "%u", GET_BIT(bits->bits, i)); + } + return result; +} + +unsigned char *bits_to_raw(const bits_t *bits) { + if (bits->bitlen == 0) { + return NULL; + } + return try_memdup(bits->bits, BYTE_LEN(bits->bitlen)); +} + +size_t bits_to_rawlen(const bits_t *bits) { + return BYTE_LEN(bits->bitlen); +} + +GEN bits_to_bitvec(const bits_t *bits) { + GEN bitvec = gtovecsmall0(gen_0, bits->bitlen); + for (size_t i = 0; i < bits->bitlen; ++i) { + if (GET_BIT(bits->bits, i) != 0) + gel(bitvec, i + 1) = (GEN)1; + } + return bitvec; +} + +static unsigned char or_func(unsigned char one, unsigned char other) { + return one | other; +} + +static unsigned char and_func(unsigned char one, unsigned char other) { + return one & other; +} + +static bits_t *bits_bitwise(const bits_t *one, const bits_t *other, + unsigned char (*bitwise_func)( + unsigned char, unsigned char)) { + const bits_t *shorter; + const bits_t *longer; + if (one->bitlen > other->bitlen) { + shorter = other; + longer = one; + } else { + shorter = one; + longer = other; + } + + bits_t *result = bits_new(longer->bitlen); + for (size_t i = 0; i < longer->bitlen; ++i) { + size_t longer_pos = longer->bitlen - i - 1; + + unsigned char longer_bit = (unsigned char)GET_BIT(longer->bits, + longer_pos); + unsigned char shorter_bit = 0; + if (shorter->bitlen > i) { + size_t shorter_pos = shorter->bitlen - i - 1; + shorter_bit = (unsigned char)GET_BIT(shorter->bits, + shorter_pos); + } + + unsigned char result_bit = bitwise_func(longer_bit, shorter_bit); + result->bits[longer_pos / 8] |= result_bit << (7 - (longer_pos % 8)); + } + + return result; +} + +bits_t *bits_or(const bits_t *one, const bits_t *other) { + return bits_bitwise(one, other, or_func); +} + +bits_t *bits_and(const bits_t *one, const bits_t *other) { + return bits_bitwise(one, other, and_func); +} + +void bits_notz(bits_t *bits) { + if (bits->bitlen == 0) + return; + for (size_t i = 0; i < bits->bitlen / 8; ++i) { + bits->bits[i] = ~bits->bits[i]; + } + if (bits->bitlen % 8 != 0) { + size_t mask_len = bits->bitlen % 8; + unsigned char mask = 0; + for (size_t i = 7; i >= 0; --i) { + mask |= 1 << i; + if (--mask_len == 0) + break; + } + size_t last_pos = (bits->bitlen / 8); + unsigned char anti_mask = ~mask; + unsigned char last_byte = bits->bits[last_pos]; + bits->bits[last_pos] = (~last_byte & mask) | (last_byte & anti_mask); + } +} + +bits_t *bits_not(const bits_t *bits) { + bits_t *result = bits_copy(bits); + bits_notz(result); + return result; +} + +void bits_rotz(bits_t *bits) { + unsigned char original_bits[bits->allocated]; + for (size_t i = 0; i < bits->allocated; ++i) { + original_bits[i] = bits->bits[i]; + bits->bits[i] = 0; + } + for (size_t i = 0; i < bits->bitlen / 2; ++i) { + size_t left_pos = i; + size_t right_pos = bits->bitlen - i - 1; + unsigned char left_bit = (unsigned char)GET_BIT(original_bits, + left_pos); + unsigned char right_bit = (unsigned char)GET_BIT(original_bits, + right_pos); + bits->bits[right_pos / 8] |= left_bit << (7 - (right_pos % 8)); + bits->bits[left_pos / 8] |= right_bit << (7 - (left_pos % 8)); + } + if (bits->bitlen % 2 == 1) { + size_t middle_pos = bits->bitlen / 2; + + unsigned char middle_bit = (unsigned char)GET_BIT(original_bits, + middle_pos); + bits->bits[middle_pos / 8] |= middle_bit << (7 - (middle_pos % 8)); + } +} + +bits_t *bits_rot(const bits_t *bits) { + bits_t *result = bits_copy(bits); + bits_rotz(result); + return result; +} + +void bits_shiftz(bits_t *bits, long amount) { + if (amount == 0) + return; + unsigned char original_bits[bits->allocated]; + for (size_t i = 0; i < bits->allocated; ++i) { + original_bits[i] = bits->bits[i]; + bits->bits[i] = 0; + } + for (size_t i = 0; i < bits->bitlen; ++i) { + unsigned char new_bit = 0; + if ((amount > 0 && i + amount < bits->bitlen) || + (amount < 0 && i >= -amount)) { + new_bit = (unsigned char)GET_BIT(original_bits, i + amount); + } + bits->bits[i / 8] |= new_bit << (7 - (i % 8)); + } +} + +bits_t *bits_shift(const bits_t *bits, long amount) { + bits_t *result = bits_copy(bits); + bits_shiftz(result, amount); + return result; +} + +void bits_shiftrz(bits_t *bits, long amount) { + if (amount == 0) + return; + unsigned char original_bits[bits->allocated]; + for (size_t i = 0; i < bits->allocated; ++i) { + original_bits[i] = bits->bits[i]; + bits->bits[i] = 0; + } + for (size_t i = 0; i < bits->bitlen; ++i) { + unsigned char new_bit = 0; + size_t new_pos = 0; + if ((amount > 0 && i + amount < bits->bitlen) || + (amount < 0 && i >= -amount)) { + new_pos = i + amount; + } else if (amount > 0) { + new_pos = (i + amount) % bits->bitlen; + } else if (amount < 0) { + long mod_amount = amount % bits->bitlen; + new_pos = (i + mod_amount) % bits->bitlen; + } + new_bit = (unsigned char)GET_BIT(original_bits, new_pos); + bits->bits[i / 8] |= new_bit << (7 - (i % 8)); + } +} + +bits_t *bits_shiftr(const bits_t *bits, long amount) { + bits_t *result = bits_copy(bits); + bits_shiftrz(result, amount); + return result; +} + +bool bits_eq(const bits_t *one, const bits_t *other) { + if (one->bitlen != other->bitlen) + return false; + if (one->bitlen == 0) + return true; + if (memcmp(one->bits, other->bits, one->bitlen / 8) != 0) + return false; + if (one->bitlen % 8 != 0) { + size_t mask_len = one->bitlen % 8; + unsigned char mask = 0; + for (size_t i = 7; i >= 0; --i) { + mask |= 1 << i; + if (--mask_len == 0) + break; + } + size_t last_byte = (one->bitlen / 8); + unsigned char one_masked = one->bits[last_byte] & mask; + unsigned char other_masked = other->bits[last_byte] & mask; + return one_masked == other_masked; + } + return true; +} diff --git a/src/util/bits.h b/src/util/bits.h index 08c06d1..42ab899 100644 --- a/src/util/bits.h +++ b/src/util/bits.h @@ -1,5 +1,65 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017 J08nY + */ #ifndef ECGEN_BITS_H #define ECGEN_BITS_H +#include "gen/types.h" + +#define BYTE_LEN(bit_len) (((bit_len) % 8 == 0) ? (bit_len) / 8 : ((bit_len) / 8) + 1) +#define GET_BIT(bit_array, bit_pos) (((bit_array)[(bit_pos) / 8] & (1 << (7 - ((bit_pos) % 8)))) >> (7 - ((bit_pos) % 8))) + +bits_t *bits_new(size_t bit_len); + +bits_t *bits_copy(const bits_t *bits); + +void bits_free(bits_t **bits); + +bits_t *bits_from_i(GEN i); + +bits_t *bits_from_hex(const char *hex_str); + +bits_t *bits_from_bin(const char *bin_str); + +bits_t *bits_from_raw(const unsigned char *bits, size_t bit_len); + +bits_t *bits_from_bitvec(GEN v); + +GEN bits_to_i(const bits_t *bits); + +char *bits_to_hex(const bits_t *bits); + +char *bits_to_bin(const bits_t *bits); + +unsigned char *bits_to_raw(const bits_t *bits); + +size_t bits_to_rawlen(const bits_t *bits); + +GEN bits_to_bitvec(const bits_t *bits); + +bits_t *bits_or(const bits_t *one, const bits_t *other); + +bits_t *bits_and(const bits_t *one, const bits_t *other); + +void bits_notz(bits_t *bits); + +bits_t *bits_not(const bits_t *bits); + +void bits_rotz(bits_t *bits); + +bits_t *bits_rot(const bits_t *bits); + +void bits_shiftz(bits_t *bits, long amount); + +bits_t *bits_shift(const bits_t *bits, long amount); + +void bits_shiftrz(bits_t *bits, long amount); + +bits_t *bits_shiftr(const bits_t *bits, long amount); + +bool bits_eq(const bits_t *one, const bits_t *other); + + #endif //ECGEN_BITS_H diff --git a/test/src/util/test_bits.c b/test/src/util/test_bits.c new file mode 100644 index 0000000..7b5a896 --- /dev/null +++ b/test/src/util/test_bits.c @@ -0,0 +1,346 @@ +/* + * ecgen, tool for generating Elliptic curve domain parameters + * Copyright (C) 2017 J08nY + */ + +#include <criterion/criterion.h> +#include <gen/types.h> +#include "util/bits.h" +#include "util/memory.h" +#include "test/default.h" + +TestSuite(bits, .init = default_setup, .fini = default_teardown); + + +Test(bits, test_bits_new) { + bits_t *bits = bits_new(10); + cr_assert_not_null(bits,); + cr_assert_eq(bits->bitlen, 10,); + cr_assert_eq(bits->allocated, 2,); + cr_assert_eq(bits->bits[0], 0,); + cr_assert_eq(bits->bits[1], 0,); + bits_free(&bits); +} + +Test(bits, test_bits_copy) { + bits_t *bits = bits_new(10); + bits->bits[0] = 0b10101010; + bits->bits[1] = 0b11000000; + + bits_t *other_bits = bits_copy(bits); + cr_assert_not_null(other_bits,); + cr_assert_eq(other_bits->allocated, bits->allocated,); + cr_assert_eq(other_bits->bitlen, bits->bitlen,); + cr_assert_eq(other_bits->bits[0], bits->bits[0],); + cr_assert_eq(other_bits->bits[1], bits->bits[1],); + bits_free(&bits); + bits_free(&other_bits); +} + +Test(bits, test_bits_from_i) { + GEN i = int2n(5); + + bits_t *bits = bits_from_i(i); + cr_assert_not_null(bits,); + cr_assert_eq(bits->bitlen, 6,); + cr_assert_eq(bits->allocated, 1,); + cr_assert_eq(bits->bits[0], 0b10000000,); + bits_free(&bits); +} + +Test(bits, test_bits_from_hex) { + char *hex = "0ab"; + + bits_t *bits = bits_from_hex(hex); + cr_assert_not_null(bits,); + cr_assert_eq(bits->bitlen, 12,); + cr_assert_eq(bits->allocated, 2,); + cr_assert_eq(bits->bits[0], 0x0a,); + cr_assert_eq(bits->bits[1], 0xb0,); + bits_free(&bits); +} + +Test(bits, test_bits_from_bin) { + char *bin = "000010101101"; + + bits_t *bits = bits_from_bin(bin); + cr_assert_not_null(bits,); + cr_assert_eq(bits->bitlen, 12,); + cr_assert_eq(bits->allocated, 2,); + cr_assert_eq(bits->bits[0], 0b00001010,); + cr_assert_eq(bits->bits[1], 0b11010000,); + bits_free(&bits); +} + +Test(bits, test_bits_from_raw) { + unsigned char *raw = (unsigned char *)"\x0a\xb0"; + + bits_t *bits = bits_from_raw(raw, 16); + cr_assert_not_null(bits,); + cr_assert_eq(bits->bitlen, 16,); + cr_assert_eq(bits->allocated, 2,); + cr_assert_eq(bits->bits[0], 0x0a,); + cr_assert_eq(bits->bits[1], 0xb0,); + bits_free(&bits); +} + +Test(bits, test_bits_from_bitvec) { + GEN bitvec = binary_zv(int2n(5)); + + bits_t *bits = bits_from_bitvec(bitvec); + cr_assert_not_null(bits,); + cr_assert_eq(bits->bitlen, 6,); + cr_assert_eq(bits->allocated, 1,); + cr_assert_eq(bits->bits[0], 0b10000000,); + bits_free(&bits); +} + +Test(bits, test_bits_to_i) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + GEN i = bits_to_i(bits); + cr_assert_not_null(bits,); + cr_assert(gequal(i, int2n(5)),); + bits_free(&bits); +} + +Test(bits, test_bits_to_hex) { + bits_t *bits = bits_new(12); + bits->bits[0] = 0xab; + bits->bits[1] = 0xc0; + + char *hex = bits_to_hex(bits); + cr_assert_not_null(hex,); + cr_assert_str_eq(hex, "abc0",); + try_free(hex); + bits_free(&bits); +} + +Test(bits, test_bits_to_bin) { + bits_t *bits = bits_new(12); + bits->bits[0] = 0b10101010; + bits->bits[1] = 0b11110000; + + char *bin = bits_to_bin(bits); + cr_assert_not_null(bin,); + cr_assert_str_eq(bin, "101010101111",); + try_free(bin); + bits_free(&bits); +} + +Test(bits, test_bits_to_raw) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + unsigned char *raw = bits_to_raw(bits); + size_t rawlen = bits_to_rawlen(bits); + cr_assert_not_null(raw,); + cr_assert_eq(rawlen, 1,); + cr_assert_eq(raw[0], 0b10000000,); + try_free(raw); + bits_free(&bits); +} + +Test(bits, test_bits_to_bitvec) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + GEN bitvec = bits_to_bitvec(bits); + cr_assert_not_null(bitvec,); + cr_assert(gequal(bitvec, binary_zv(int2n(5))),); +} + +Test(bits, test_bits_or) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + bits_t *other_bits = bits_new(10); + other_bits->bits[0] = 0b00000000; + other_bits->bits[1] = 0b11000000; + + bits_t *or = bits_or(bits, other_bits); + cr_assert_not_null(or,); + cr_assert_eq(or->bitlen, 10,); + cr_assert_eq(or->bits[0], 0b00001000,); + cr_assert_eq(or->bits[1], 0b11000000,); + bits_free(&bits); + bits_free(&other_bits); + bits_free(&or); +} + +Test(bits, test_bits_and) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + bits_t *other_bits = bits_new(10); + other_bits->bits[0] = 0b00001000; + other_bits->bits[1] = 0b11000000; + + bits_t *and = bits_and(bits, other_bits); + cr_assert_not_null(and,); + cr_assert_eq(and->bitlen, 10,); + cr_assert_eq(and->bits[0], 0b00001000,); + cr_assert_eq(and->bits[1], 0b00000000,); + bits_free(&bits); + bits_free(&other_bits); + bits_free(&and); +} + +Test(bits, test_bits_notz) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + bits_notz(bits); + cr_assert_eq(bits->bitlen, 6,); + cr_assert_eq(bits->bits[0], 0b01111100,); + bits_free(&bits); +} + +Test(bits, test_bits_not) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + bits_t *not = bits_not(bits); + cr_assert_not_null(not,); + cr_assert_eq(not->bitlen, 6,); + cr_assert_eq(not->bits[0], 0b01111100,); + bits_free(&bits); + bits_free(¬); +} + +Test(bits, test_bits_rotz) { + bits_t *bits = bits_new(10); + bits->bits[0] = 0b11111000; + bits->bits[1] = 0b00000000; + + bits_rotz(bits); + cr_assert_eq(bits->bitlen, 10,); + cr_assert_eq(bits->bits[0], 0b00000111,); + cr_assert_eq(bits->bits[1], 0b11000000,); + bits_free(&bits); +} + +Test(bits, test_bits_rot) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + bits_t *rot = bits_rot(bits); + cr_assert_not_null(rot,); + cr_assert_eq(rot->bitlen, 6,); + cr_assert_eq(rot->bits[0], 0b00000100,); + bits_free(&bits); + bits_free(&rot); + + bits = bits_new(5); + bits->bits[0] = 0b10100000; + + rot = bits_rot(bits); + cr_assert_not_null(rot,); + cr_assert_eq(rot->bitlen, 5,); + cr_assert_eq(rot->bits[0], 0b00101000,); + bits_free(&bits); + bits_free(&rot); +} + +Test(bits, test_bits_shiftz) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10101000; + + bits_shiftz(bits, -1); + cr_assert_eq(bits->bitlen, 6,); + cr_assert_eq(bits->bits[0], 0b01010100,); + bits_free(&bits); +} + +Test(bits, test_bits_shift) { + bits_t *bits = bits_new(8); + bits->bits[0] = 0b11001100; + + bits_t *shift = bits_shift(bits, 2); + cr_assert_not_null(shift,); + cr_assert_eq(shift->bitlen, 8,); + cr_assert_eq(shift->bits[0], 0b00110000,); + bits_free(&bits); + bits_free(&shift); +} + +Test(bits, test_bits_shiftrz) { + bits_t *bits = bits_new(8); + bits->bits[0] = 0b11001100; + + bits_shiftrz(bits, 1); + cr_assert_eq(bits->bitlen, 8,); + cr_assert_eq(bits->bits[0], 0b10011001,); + bits->bits[0] = 0b11001100; + + bits_shiftrz(bits, 9); + cr_assert_eq(bits->bitlen, 8,); + cr_assert_eq(bits->bits[0], 0b10011001,); + bits->bits[0] = 0b11001100; + + bits_shiftrz(bits, -10); + cr_assert_eq(bits->bitlen, 8,); + cr_assert_eq(bits->bits[0], 0b00110011,); + bits_free(&bits); +} + +Test(bits, test_bits_shiftr) { + bits_t *bits = bits_new(8); + bits->bits[0] = 0b11001100; + + bits_t *shift = bits_shiftr(bits, 1); + cr_assert_eq(shift->bitlen, 8,); + cr_assert_eq(shift->bits[0], 0b10011001,); + bits_free(&bits); + bits_free(&shift); +} + +Test(bits, test_bits_eq) { + bits_t *bits = bits_new(6); + bits->bits[0] = 0b10000000; + + bits_t *other_bits = bits_new(6); + other_bits->bits[0] = 0b10000000; + + cr_assert(bits_eq(bits, other_bits),); + + bits->bits[0] = 0b10010000; + other_bits->bits[0] = 0b10000000; + + cr_assert_not(bits_eq(bits, other_bits),); + + bits_free(&bits); + bits_free(&other_bits); +} + +Test(bits, test_bits_eq_len) { + bits_t *bits = bits_new(5); + bits->bits[0] = 0b10000000; + + bits_t *other_bits = bits_new(6); + other_bits->bits[0] = 0b10000000; + cr_assert_not(bits_eq(bits, other_bits),); + bits_free(&bits); + bits_free(&other_bits); +} + +Test(bits, test_bits_eq_large) { + bits_t *bits = bits_new(10); + bits->bits[0] = 0b10000010; + bits->bits[1] = 0b11000000; + + bits_t *other_bits = bits_new(10); + other_bits->bits[0] = 0b10000010; + other_bits->bits[1] = 0b11000000; + + cr_assert(bits_eq(bits, other_bits),); + + bits->bits[0] = 0b10000000; + other_bits->bits[0] = 0b00000010; + + cr_assert_not(bits_eq(bits, other_bits),); + + bits_free(&bits); + bits_free(&other_bits); +} |