bliss_fft.h bliss_fft.c \
bliss_huffman_code.h bliss_huffman_code.c \
bliss_huffman_code_1.c bliss_huffman_code_3.c bliss_huffman_code_4.c \
+ bliss_huffman_coder.h bliss_huffman_coder.c \
bliss_sampler.h bliss_sampler.c
libbliss_la_LIBADD = libbliss-params.la
}
-#define NO_NODE -1
-#define NO_TUPLE -1
-
static void write_node(node_t *node)
{
int16_t node_0, node_1, tuple;
- node_0 = node->l ? node->l->index : NO_NODE;
- node_1 = node->r ? node->r->index : NO_NODE;
- tuple = node->tuple ? node->tuple->index : NO_TUPLE;
+ node_0 = node->l ? node->l->index : BLISS_HUFFMAN_CODE_NO_NODE;
+ node_1 = node->r ? node->r->index : BLISS_HUFFMAN_CODE_NO_NODE;
+ tuple = node->tuple ? node->tuple->index : BLISS_HUFFMAN_CODE_NO_TUPLE;
+
printf("\t{ %3d, %3d, %3d }, /* %3d: ", node_0, node_1, tuple, node->index);
if (node->tuple)
uint16_t bits;
};
+#define BLISS_HUFFMAN_CODE_NO_TUPLE -1
+#define BLISS_HUFFMAN_CODE_NO_NODE -1
+
struct bliss_huffman_code_node_t {
int16_t node_0;
int16_t node_1;
--- /dev/null
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * 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. See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * This program is distributed in the hope that it will be useful, but
+ * WITHOUT ANY WARRANTY;https://www.hsr.ch/HSR-intern-Anmeldung.4409.0.html?&no_cache=1 without even the implied warranty of MERCHANTABILITY
+ * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
+ * for more details.
+ */
+
+#include "bliss_huffman_coder.h"
+
+typedef struct private_bliss_huffman_coder_t private_bliss_huffman_coder_t;
+
+/**
+ * Private data structure for bliss_huffman_coder_t object
+ */
+struct private_bliss_huffman_coder_t {
+ /**
+ * Public interface.
+ */
+ bliss_huffman_coder_t public;
+
+ /**
+ * Bitpacker to write to or read from
+ */
+ bliss_bitpacker_t *packer;
+
+ /**
+ * Huffman code table to be used
+ */
+ bliss_huffman_code_t *code;
+
+ /**
+ * Maximum index into tuples table
+ */
+ int index_max;
+
+ /**
+ * Number of encoded or decoded bits
+ */
+ size_t bits;
+
+};
+
+METHOD(bliss_huffman_coder_t, get_bits, size_t,
+ private_bliss_huffman_coder_t *this)
+{
+ return this->bits;
+}
+
+METHOD(bliss_huffman_coder_t, encode, bool,
+ private_bliss_huffman_coder_t *this, int32_t z1, int16_t z2)
+{
+ uint32_t code;
+ uint16_t bits;
+ int index;
+
+ index = z1 * (2*this->code->n_z2 - 1) + z2 + this->code->n_z2 - 1;
+ if (index >= this->index_max)
+ {
+ DBG1(DBG_LIB, "index exceeded in Huffman encoding table");
+ return FALSE;
+ }
+ code = this->code->tuples[index].code;
+ bits = this->code->tuples[index].bits;
+ if (!this->packer->write_bits(this->packer, code, bits))
+ {
+ DBG1(DBG_LIB, "bitpacker exceeded its buffer");
+ return FALSE;
+ }
+ this->bits += bits;
+
+ return TRUE;
+}
+
+METHOD(bliss_huffman_coder_t, decode, bool,
+ private_bliss_huffman_coder_t *this, int32_t *z1, int16_t *z2)
+{
+ bliss_huffman_code_node_t *node;
+ uint32_t bit;
+
+ node = this->code->nodes;
+ while (node->tuple == BLISS_HUFFMAN_CODE_NO_TUPLE)
+ {
+ if (node->node_0 == BLISS_HUFFMAN_CODE_NO_NODE ||
+ node->node_1 == BLISS_HUFFMAN_CODE_NO_NODE)
+ {
+ DBG1(DBG_LIB, "error in Huffman decoding table");
+ return FALSE;
+ }
+ if (!this->packer->read_bits(this->packer, &bit, 1))
+ {
+ DBG1(DBG_LIB, "bitpacker depleted its buffer");
+ return FALSE;
+ }
+ node = &this->code->nodes[bit ? node->node_1 : node->node_0];
+ this->bits++;
+ }
+ *z1 = node->tuple / (2*this->code->n_z2 - 1);
+ *z2 = node->tuple - (2*this->code->n_z2 - 1) * (*z1) - this->code->n_z2 + 1;
+
+ return TRUE;
+}
+
+METHOD(bliss_huffman_coder_t, destroy, void,
+ private_bliss_huffman_coder_t *this)
+{
+ free(this);
+}
+
+/**
+ * See header.
+ */
+bliss_huffman_coder_t *bliss_huffman_coder_create(bliss_huffman_code_t *code,
+ bliss_bitpacker_t *packer)
+{
+ private_bliss_huffman_coder_t *this;
+
+ INIT(this,
+ .public = {
+ .get_bits = _get_bits,
+ .encode = _encode,
+ .decode = _decode,
+ .destroy = _destroy,
+ },
+ .packer = packer,
+ .code = code,
+ .index_max = (2*code->n_z2 - 1) * code->n_z1,
+ );
+
+ return &this->public;
+}
--- /dev/null
+/*
+ * Copyright (C) 2014 Andreas Steffen
+ * HSR Hochschule fuer Technik Rapperswil
+ *
+ * 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. See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * 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.
+ */
+
+/**
+ * @defgroup bliss_huffman_coder bliss_huffman_coder
+ * @{ @ingroup bliss_p
+ */
+
+#ifndef BLISS_HUFFMAN_CODER_H_
+#define BLISS_HUFFMAN_CODER_H_
+
+#include "bliss_huffman_code.h"
+#include "bliss_bitpacker.h"
+
+#include <library.h>
+
+typedef struct bliss_huffman_coder_t bliss_huffman_coder_t;
+
+/**
+ * Encodes and decodes binary Huffman codes
+ */
+struct bliss_huffman_coder_t {
+
+ /**
+ * Get number of encoded or decoded bits
+ *
+ * @result Number of bits
+ */
+ size_t (*get_bits)(bliss_huffman_coder_t *this);
+
+ /**
+ * Encode a (z1, z2) tuple using a Huffman code
+ *
+ * @param z1 z1 value to be encoded
+ * @param z2 z2 value to be encoded
+ * @result TRUE if value could be encoded
+ */
+ bool (*encode)(bliss_huffman_coder_t *this, int32_t z1, int16_t z2);
+
+
+ /**
+ * Decode a (z1, z2) tuple using a Huffman code
+ *
+ * @param z1 Decoded z1 value returned
+ * @param z2 Decoded z2 value returned
+ * @result TRUE if value could be decoded from bitpacker
+ */
+ bool (*decode)(bliss_huffman_coder_t *this, int32_t *z1, int16_t *z2);
+
+ /**
+ * Destroy bliss_huffman_coder_t object
+ */
+ void (*destroy)(bliss_huffman_coder_t *this);
+};
+
+/**
+ * Create a bliss_huffman_coder_t object
+ *
+ * @param code Huffman code table
+ * @param packer Bitpacker to write to or read from
+ */
+bliss_huffman_coder_t* bliss_huffman_coder_create(bliss_huffman_code_t *code,
+ bliss_bitpacker_t *packer);
+
+#endif /** BLISS_HUFFMAN_CODER_H_ @}*/
{
continue;
}
+
+ *signature = sig->get_encoding(sig);
+ if (signature->len == 0)
+ {
+ DBG1(DBG_LIB, "inefficient Huffman coding of signature");
+ continue;
+ }
DBG2(DBG_LIB, "signature generation needed %u round%s", tests,
(tests == 1) ? "" : "s");
break;
}
success = TRUE;
- *signature = sig->get_encoding(sig);
-
end:
/* cleanup */
sampler->destroy(sampler);
#include "bliss_signature.h"
#include "bliss_bitpacker.h"
+#include "bliss_huffman_coder.h"
typedef struct private_bliss_signature_t private_bliss_signature_t;
private_bliss_signature_t *this)
{
bliss_bitpacker_t *packer;
+ bliss_huffman_coder_t *coder;
+ bliss_huffman_code_t *code;
+ int32_t z1;
+ uint32_t z1_sign;
uint16_t z2d_bits;
- chunk_t encoding;
+ chunk_t encoding = chunk_empty;
int i;
z2d_bits = this->set->z1_bits - this->set->d;
+ /* Get Huffman code for this BLISS parameter set */
+ code = bliss_huffman_code_get_by_id(this->set->id);
+ if (!code)
+ {
+ DBG1(DBG_LIB, "no Huffman code found for parameter set %N",
+ bliss_param_set_id_names, this->set->id);
+ return chunk_empty;
+ }
+
packer = bliss_bitpacker_create(this->set->n * this->set->z1_bits +
this->set->n * z2d_bits +
this->set->kappa * this->set->n_bits);
+ coder = bliss_huffman_coder_create(code, packer);
for (i = 0; i < this->set->n; i++)
{
- packer->write_bits(packer, this->z1[i], this->set->z1_bits);
- }
- for (i = 0; i < this->set->n; i++)
- {
- packer->write_bits(packer, this->z2d[i], z2d_bits);
+ /* determine and remove the sign of z1[i]*/
+ z1_sign = this->z1[i] < 0;
+ z1 = z1_sign ? -this->z1[i] : this->z1[i];
+
+ if (!packer->write_bits(packer, z1_sign, 1) ||
+ !packer->write_bits(packer, z1 & 0xff, 8) ||
+ !coder->encode(coder, z1 >> 8, this->z2d[i]))
+ {
+ goto end;
+ }
}
for (i = 0; i < this->set->kappa; i++)
{
- packer->write_bits(packer, this->c_indices[i], this->set->n_bits);
+ if (!packer->write_bits(packer, this->c_indices[i], this->set->n_bits))
+ {
+ goto end;
+ }
}
encoding = packer->extract_buf(packer);
+ DBG2(DBG_LIB, "efficiency of Huffman coder is %6.4f bits/tuple (%u bits)",
+ coder->get_bits(coder)/(double)(this->set->n),
+ coder->get_bits(coder));
DBG2(DBG_LIB, "generated BLISS signature (%u bits encoded in %u bytes)",
packer->get_bits(packer), encoding.len);
- packer->destroy(packer);
+ end:
+ coder->destroy(coder);
+ packer->destroy(packer);
return encoding;
}
{
private_bliss_signature_t *this;
bliss_bitpacker_t *packer;
- uint32_t z1_sign, z1_mask, value;
- uint16_t z2d_sign, z2d_mask, z1_bits, z2d_bits;
+ bliss_huffman_coder_t *coder;
+ bliss_huffman_code_t *code;
+ uint32_t z1_sign, z1_low, value;
+ int32_t z1;
+ int16_t z2;
int i;
- z1_bits = set->z1_bits;
- z2d_bits = set->z1_bits - set->d;
-
- if (8 * encoding.len < set->n * set->z1_bits + set->n * z2d_bits +
- set->kappa * set->n_bits)
+ /* Get Huffman code for this BLISS parameter set */
+ code = bliss_huffman_code_get_by_id(set->id);
+ if (!code)
{
- DBG1(DBG_LIB, "incorrect BLISS signature size");
+ DBG1(DBG_LIB, "no Huffman code found for parameter set %N",
+ bliss_param_set_id_names, set->id);
return NULL;
}
);
packer = bliss_bitpacker_create_from_data(encoding);
-
- z1_sign = 1 << (z1_bits - 1);
- z1_mask = ((1 << (32 - z1_bits)) - 1) << z1_bits;
+ coder = bliss_huffman_coder_create(code, packer);
for (i = 0; i < set->n; i++)
{
- packer->read_bits(packer, &value, z1_bits);
- this->z1[i] = value & z1_sign ? value | z1_mask : value;
+ if (!packer->read_bits(packer, &z1_sign, 1) ||
+ !packer->read_bits(packer, &z1_low, 8) ||
+ !coder->decode(coder, &z1, &z2))
+ {
+ coder->destroy(coder);
+ packer->destroy(packer);
+ destroy(this);
+ return NULL;
+ }
+ z1 = (z1 << 8) + z1_low;
+ this->z1[i] = z1_sign ? -z1 : z1;
+ this->z2d[i] = z2;
}
+ coder->destroy(coder);
- z2d_sign = 1 << (z2d_bits - 1);
- z2d_mask = ((1 << (16 - z2d_bits)) - 1) << z2d_bits;
-
- for (i = 0; i < set->n; i++)
- {
- packer->read_bits(packer, &value, z2d_bits);
- this->z2d[i] = value & z2d_sign ? value | z2d_mask : value;
- }
for (i = 0; i < set->kappa; i++)
{
- packer->read_bits(packer, &value, set->n_bits);
+ if (!packer->read_bits(packer, &value, set->n_bits))
+ {
+ packer->destroy(packer);
+ destroy(this);
+ return NULL;
+ }
this->c_indices[i] = value;
}
packer->destroy(packer);
projects / strongswan.git / commitdiff