/* vim: set expandtab ts=4 sw=4: */
/*
* You may redistribute this program and/or modify it under the terms of
* the GNU General Public License as published by the Free Software Foundation,
* either version 3 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, see .
*/
#include "benc/String.h"
#include "crypto/random/Random.h"
#include "switch/EncodingScheme.h"
#define NumberCompress_OLD_CODE
#include "switch/NumberCompress.h"
#include "memory/Allocator.h"
#include "util/Bits.h"
#define Order_TYPE struct EncodingScheme_Form
#define Order_NAME OfEncodingForms
#define Order_COMPARE compareEncodingForms
#include "util/Order.h"
static inline int compareEncodingForms(const struct EncodingScheme_Form* a,
const struct EncodingScheme_Form* b)
{
int diff = a->bitCount;
diff -= b->bitCount;
return diff == 0 ? 0 : diff > 0 ? 1 : -1;
}
static void randomForm(struct EncodingScheme_Form* form, struct Random* rand)
{
for (;;) {
Random_bytes(rand, (uint8_t*)form, sizeof(struct EncodingScheme_Form));
//Bits_memset(form, 0xff, sizeof(struct EncodingScheme_Form));
form->bitCount &= ((1<<5)-1);
if (!form->bitCount) {
form->bitCount++;
}
form->prefixLen &= ((1<<5)-1);
if (!form->prefixLen) {
form->prefixLen++;
}
if (EncodingScheme_formSize(form) > 59) { continue; }
if (form->prefixLen > 3 && (form->prefix & 0xf) == 1) { continue; }
break;
}
form->prefix &= ((((uint64_t)1)<prefixLen)-1);
}
static struct EncodingScheme* randomScheme(struct Random* rand, struct Allocator* alloc)
{
struct EncodingScheme* out =
Allocator_malloc(alloc, sizeof(struct EncodingScheme));
do {
out->count = Random_uint32(rand) % 32;
} while (out->count < 2);
out->forms = Allocator_malloc(alloc, sizeof(struct EncodingScheme_Form) * out->count);
for (int i = 0; i < (int)out->count; i++) {
randomForm(&out->forms[i], rand);
for (int j = 0; j < i; j++) {
if (out->forms[i].bitCount == out->forms[j].bitCount) {
i--;
break;
}
int minPfx = (out->forms[i].prefixLen < out->forms[j].prefixLen)
? out->forms[i].prefixLen : out->forms[j].prefixLen;
if (((out->forms[j].prefix ^ out->forms[i].prefix) & ((1<forms[j],
&out->forms[i-1],
sizeof(struct EncodingScheme_Form));
}
i -= 2;
break;
}
}
}
Order_OfEncodingForms_qsort(out->forms, out->count);
return out;
}
static void assertEqual(struct EncodingScheme* a,
struct EncodingScheme* b)
{
Assert_true(b);
Assert_true(a->count == b->count);
Assert_true(
!Bits_memcmp(a->forms, b->forms, sizeof(struct EncodingScheme_Form) * a->count));
}
static void randomTest(struct Allocator* parent, struct Random* rand)
{
struct Allocator* alloc = Allocator_child(parent);
struct EncodingScheme* control = randomScheme(rand, alloc);
String* data = EncodingScheme_serialize(control, alloc);
struct EncodingScheme* test = EncodingScheme_deserialize(data, alloc);
assertEqual(control, test);
Allocator_free(alloc);
}
// Just make sure random crap doesn't crash it.
static void fuzzTest(struct Allocator* parent, struct Random* rand)
{
struct Allocator* alloc = Allocator_child(parent);
String* data = String_newBinary(NULL, Random_uint32(rand) % 1024, alloc);
Random_bytes(rand, (uint8_t*)data->bytes, data->len);
EncodingScheme_deserialize(data, alloc);
Allocator_free(alloc);
}
/** Greatest possible number using x bits, all are set. */
#define Bits_maxBits64(x) ((((uint64_t)1)<<(x))-1)
static void encoding(struct Allocator* parent)
{
struct EncodingScheme_Form forms[3] = {
{
.prefixLen = 15,
.bitCount = 2,
.prefix = ((1<<15)-1) ^ (1<<1),
}, {
.prefixLen = 20,
.bitCount = 4,
.prefix = ((1<<20)-1) ^ (1<<2),
}, {
.prefixLen = 18,
.bitCount = 8,
.prefix = ((1<<18)-1) ^ (1<<3),
}
};
// should encode as prefixLen, bitCount, prefix
// 111111111111101 00010 01111 15/2/~0 -> 01001111 11110100 11111111 remainder 1
// 11111111111111111011 00100 10100 20/4/~0 -> 00101001 11011001 11111111 remainder 7f
// 111111111111110111 01000 10010 18/8/~0 -> 01111111 10001001 11101110 11111111 remainder 7
// 00000111 <-- appliation of remainder
//
// In bytes:
// 01001111 11110100 11111111 00101001 11011001 11111111
// 01111111 10001001 11101110 11111111 00000111
//
// or \x4f\xf4\xff\x29\xd9\xff\x7f\x89\xee\xff\x07
struct EncodingScheme list = {
.count = 3,
.forms = forms
};
struct Allocator* alloc = Allocator_child(parent);
String* data = EncodingScheme_serialize(&list, alloc);
Assert_true(data->len == 11);
Assert_true(!Bits_memcmp(data->bytes, "\x4f\xf4\xff\x29\xd9\xff\x7f\x89\xee\xff\x07", 11));
Allocator_free(alloc);
}
#define convertLabel_SELF_ROUTE 1
#define convertLabel_TOO_BIG 2
static int convertLabel(struct EncodingScheme_Form* iform,
struct EncodingScheme_Form* oform,
uint64_t label)
{
struct {
struct EncodingScheme scheme;
struct EncodingScheme_Form forms[2];
} s;
s.scheme.count = 2;
s.scheme.forms = s.forms;
Bits_memcpy(&s.forms[0], iform, sizeof(struct EncodingScheme_Form));
Bits_memcpy(&s.forms[1], oform, sizeof(struct EncodingScheme_Form));
int iformNum = 0;
int oformNum = 1;
struct EncodingScheme* scheme = &s.scheme;
Assert_true(EncodingScheme_getFormNum(scheme, label) == iformNum);
uint64_t label2 = EncodingScheme_convertLabel(scheme, label, oformNum);
if ((label & Bits_maxBits64(s.forms[0].prefixLen + s.forms[0].bitCount)) == 1) {
Assert_true(label2 == EncodingScheme_convertLabel_INVALID);
return convertLabel_SELF_ROUTE;
}
if (Bits_log2x64(label) + EncodingScheme_formSize(oform) -
EncodingScheme_formSize(iform) > 59)
{
Assert_true(label2 == EncodingScheme_convertLabel_INVALID);
return convertLabel_TOO_BIG;
}
uint64_t additional = label >> s.forms[0].prefixLen;
uint64_t director = additional & Bits_maxBits64(s.forms[0].bitCount);
if (!EncodingScheme_is358(&s.scheme)) {
} else if (1 == (s.forms[0].prefix & Bits_maxBits64(s.forms[0].prefixLen))) {
director = director - (director == 1) + (director == 0);
} else {
director += (director > 0);
}
// here is where the director is actually correct
if (!EncodingScheme_is358(&s.scheme)) {
} else if (1 == (s.forms[1].prefix & Bits_maxBits64(s.forms[1].prefixLen))) {
director = director - (director == 1) + (director == 0);
} else {
director -= (director > 0);
}
additional = additional >> s.forms[0].bitCount;
uint64_t converted = (additional << s.forms[1].bitCount) | director;
converted = (converted << s.forms[1].prefixLen) | s.forms[1].prefix;
if ((converted & Bits_maxBits64(s.forms[1].prefixLen + s.forms[1].bitCount)) == 1) {
// looks like a self-route
Assert_true(label2 == EncodingScheme_convertLabel_INVALID);
return convertLabel_SELF_ROUTE;
}
//printf("%lx == %lx", label2, converted);
Assert_true(label2 == converted);
uint64_t label3 = EncodingScheme_convertLabel(scheme, label2, iformNum);
Assert_true(label3 == label);
return 0;
}
static void convertLabelRand(struct Random* rand, struct EncodingScheme* scheme)
{
for (int i = 0; i < 100; i++) {
int oformNum;
do {
oformNum = Random_uint8(rand) % scheme->count;
} while (!oformNum);
int iformNum = Random_uint8(rand) % oformNum;
uint64_t label = Random_uint64(rand);
label &= (UINT64_MAX >> (Random_uint8(rand) % 63));
for (;;) {
// make sure the label has the right prefix
label <<= scheme->forms[iformNum].prefixLen;
label |= scheme->forms[iformNum].prefix;
Assert_true(EncodingScheme_getFormNum(scheme, label) == iformNum);
if (Bits_log2x64(label) > 59) {
// fall through
} else {
int ret = convertLabel(&scheme->forms[iformNum], &scheme->forms[oformNum], label);
if (ret == convertLabel_SELF_ROUTE) {
i--;
break;
} else if (ret == convertLabel_TOO_BIG) {
// fall through
} else if (!ret) {
// success
break;
} else {
Assert_true(0);
}
}
label >>= scheme->forms[iformNum].prefixLen + 1;
}
}
}
static void isOneHopScheme(struct Allocator* allocator)
{
struct Allocator* alloc = Allocator_child(allocator);
struct EncodingScheme* s4x8 = NumberCompress_v4x8_defineScheme(alloc);
Assert_true(!EncodingScheme_isOneHop(s4x8, 1));
Assert_true(EncodingScheme_isOneHop(s4x8, 0x21));
Assert_true(EncodingScheme_isOneHop(s4x8, 0x23));
Assert_true(!EncodingScheme_isOneHop(s4x8, 0x12));
Assert_true(EncodingScheme_isOneHop(s4x8, 0x220));
Assert_true(EncodingScheme_isOneHop(s4x8, 0x210));
Assert_true(!EncodingScheme_isOneHop(s4x8, 0x110));
struct EncodingScheme* s3x5x8 = NumberCompress_v3x5x8_defineScheme(alloc);
Assert_true(!EncodingScheme_isOneHop(s3x5x8, 1));
Assert_true(EncodingScheme_isOneHop(s3x5x8, 0x13));
Assert_true(EncodingScheme_isOneHop(s3x5x8, 0x15));
Assert_true(EncodingScheme_isOneHop(s3x5x8, 0x96));
Assert_true(EncodingScheme_isOneHop(s3x5x8, 0x400));
Assert_true(!EncodingScheme_isOneHop(s3x5x8, 0x115));
Assert_true(!EncodingScheme_isOneHop(s3x5x8, 0x166));
Assert_true(!EncodingScheme_isOneHop(s3x5x8, 0x1400));
Allocator_free(alloc);
}
typedef uint64_t (* EncodeNum)(uint32_t num);
typedef uint32_t (* DecodeNum)(uint64_t label);
static uint64_t encode358(uint32_t num)
{
uint32_t bits = NumberCompress_v3x5x8_bitsUsedForNumber(num);
return NumberCompress_v3x5x8_getCompressed(num, bits);
}
static uint32_t decode358(uint64_t label)
{
uint32_t bits = NumberCompress_v3x5x8_bitsUsedForLabel(label);
return NumberCompress_v3x5x8_getDecompressed(label, bits);
}
static uint64_t encode48(uint32_t num)
{
uint32_t bits = NumberCompress_v4x8_bitsUsedForNumber(num);
return NumberCompress_v4x8_getCompressed(num, bits);
}
static uint32_t decode48(uint64_t label)
{
uint32_t bits = NumberCompress_v4x8_bitsUsedForLabel(label);
return NumberCompress_v4x8_getDecompressed(label, bits);
}
static uint64_t encodef4(uint32_t num)
{
uint32_t bits = NumberCompress_f4_bitsUsedForNumber(num);
return NumberCompress_f4_getCompressed(num, bits);
}
static uint32_t decodef4(uint64_t label)
{
uint32_t bits = NumberCompress_f4_bitsUsedForLabel(label);
return NumberCompress_f4_getDecompressed(label, bits);
}
static void parseSerializeDir(struct EncodingScheme* scheme, EncodeNum en, DecodeNum dn)
{
int max = Bits_maxBits64(scheme->forms[scheme->count - 1].bitCount);
for (int i = 0; i <= max; i++) {
//printf("\nTest [%d]\n", i);
uint64_t dir = EncodingScheme_serializeDirector(scheme, i, -1);
//printf("[%lu] == [%lu] (%d)\n", dir, en(i), i);
Assert_true(dir == en(i));
if (dir < ~0ull) {
int out = EncodingScheme_parseDirector(scheme, dir);
//printf("Test [%d] == [%u] decode(%lu)\n", i, (uint32_t)dn(dir), dir);
Assert_true((uint32_t)i == dn(dir));
//printf("[%d] == [%d]\n", i, out);
Assert_true(i == out);
}
for (int j = 0; j < scheme->count; j++) {
if (i >> scheme->forms[j].bitCount) { continue; }
//printf(" With form [%d]\n", j);
dir = scheme->forms[j].prefix | ( i << scheme->forms[j].prefixLen );
int out = EncodingScheme_parseDirector(scheme, dir);
Assert_true(out >= 0);
uint64_t dir2 = EncodingScheme_serializeDirector(scheme, out, j);
//printf(" [%lu] == [%lu] encode(%d)\n", dir2, dir, out);
Assert_true(dir2 == dir);
}
}
}
static void bitsUsed(struct EncodingScheme* es, DecodeNum getBits, struct Random* rand)
{
uint64_t label = Random_uint64(rand);
int fn = EncodingScheme_getFormNum(es, label);
Assert_true(fn > -1);
uint32_t bits = getBits(label);
uint32_t esbits = es->forms[fn].bitCount + es->forms[fn].prefixLen;
//printf("%lx %u %u\n", label, bits, esbits);
Assert_true(bits == esbits);
}
int main()
{
struct Allocator* alloc = Allocator_new(20000000);
struct Random* rand = NULL;
Err_assert(Random_new(&rand, alloc, NULL));
encoding(alloc);
isOneHopScheme(alloc);
for (int i = 0; i < 1000; i++) {
randomTest(alloc, rand);
}
for (int i = 0; i < 1000; i++) {
fuzzTest(alloc, rand);
}
struct EncodingScheme* es48 = NumberCompress_v4x8_defineScheme(alloc);
struct EncodingScheme* es358 = NumberCompress_v3x5x8_defineScheme(alloc);
struct EncodingScheme* esf4 = NumberCompress_f4_defineScheme(alloc);
for (int i = 0; i < 1000; i++) {
bitsUsed(es48, NumberCompress_v4x8_bitsUsedForLabel, rand);
}
for (int i = 0; i < 1000; i++) {
bitsUsed(es358, NumberCompress_v3x5x8_bitsUsedForLabel, rand);
}
parseSerializeDir(es358, encode358, decode358);
parseSerializeDir(es48, encode48, decode48);
parseSerializeDir(esf4, encodef4, decodef4);
// for testing individual conversions in isolation.
/*convertLabel(
&(struct EncodingScheme_Form){.bitCount = 15, .prefixLen = 20, .prefix = 792003},
&(struct EncodingScheme_Form){.bitCount = 31, .prefixLen = 30, .prefix = 385462496},
11331704259
);*/
for (int i = 0; i < 10; i++) {
struct Allocator* tempAlloc = Allocator_child(alloc);
struct EncodingScheme* scheme = randomScheme(rand, tempAlloc);
convertLabelRand(rand, scheme);
convertLabelRand(rand, es48);
convertLabelRand(rand, es358);
Allocator_free(tempAlloc);
}
struct Allocator* tempAlloc = Allocator_child(alloc);
struct EncodingScheme* scheme = NumberCompress_v3x5x8_defineScheme(alloc);
for (int i = 0; i < NumberCompress_v3x5x8_INTERFACES; i++) {
int bits = NumberCompress_bitsUsedForNumber(i);
uint64_t expected = NumberCompress_getCompressed(i, bits);
Assert_true(expected == EncodingScheme_convertLabel(scheme, expected,
EncodingScheme_convertLabel_convertTo_CANNONICAL));
}
Allocator_free(tempAlloc);
Allocator_free(alloc);
return 0;
}