[Archipelago-submits] [278] trunk/oneliner: a bit further still
nobody at rubyforge.org
nobody at rubyforge.org
Mon May 21 05:46:16 EDT 2007
Revision: 278
Author: zond
Date: 2007-05-21 05:46:16 -0400 (Mon, 21 May 2007)
Log Message:
-----------
a bit further still
Modified Paths:
--------------
trunk/oneliner/ext/oneliner_ext.c
trunk/oneliner/tests/superstring_test.rb
Modified: trunk/oneliner/ext/oneliner_ext.c
===================================================================
--- trunk/oneliner/ext/oneliner_ext.c 2007-05-19 22:04:14 UTC (rev 277)
+++ trunk/oneliner/ext/oneliner_ext.c 2007-05-21 09:46:16 UTC (rev 278)
@@ -71,6 +71,9 @@
#define RANDOM(context,max) (oneliner_context_random(context) % (max))
#define RANDFLOAT(context) ( (gdouble) oneliner_context_random(context) ) / ( (gdouble) G_MAXUINT32 )
#define RB_ONELINER(rb_obj,pointer) Data_Get_Struct(rb_obj, oneliner_superstring, pointer)
+#define ALLOC_COPY8(dst,src,len) { \
+ dst = g_new0(guint8, len + 1); \
+ memcpy(dst, src, sizeof(guint8) * len); }
#define Q 3
#define E 0.01
@@ -99,9 +102,27 @@
guint32 n_known_check_blocks;
// Whether we have decided already that we are done decoding.
gboolean decode_done;
+ // Our graph of check blocks.
+ GHashTable *graph;
} oneliner_superstring;
//
+// An as yet mysterious block.
+//
+typedef struct {
+ guint8 *sum;
+ GHashTable *source_blocks;
+} oneliner_xor_block;
+
+//
+// An insertion to do into the graph of a superstring.
+//
+typedef struct {
+ guint32 source_block_nr;
+ oneliner_xor_block *check_block;
+} oneliner_graph_insertion;
+
+//
// A random context.
//
typedef guint8 oneliner_context;
@@ -273,18 +294,18 @@
guint32 n_blocks_needed,
guint8 *data)
{
- guint32 block_no;
+ guint32 block_nr;
guint8 *tmp_block;
guint8 tmp_data[n_bytes_for_blocks];
GArray *rval = g_array_new(FALSE, FALSE, sizeof(guint8 *));
g_array_set_size(rval, n_blocks_needed);
memcpy((gchar *) tmp_data, (gchar *) data, sizeof(guint8) * data_len);
- for (block_no = 0; block_no < n_blocks_needed; block_no++) {
- guint32 pos = block_no * block_size;
+ for (block_nr = 0; block_nr < n_blocks_needed; block_nr++) {
+ guint32 pos = block_nr * block_size;
tmp_block = g_new0(guint8, n_chars_in_block + 1);
oneliner_superstring_get_block_from_data(tmp_data, pos, block_size, tmp_block);
- g_array_index(rval, guint8 *, block_no) = tmp_block;
+ g_array_index(rval, guint8 *, block_nr) = tmp_block;
}
return rval;
@@ -385,7 +406,9 @@
for (tmp = 0; tmp < str->blocks->len; tmp++) {
guint32 aux_block_nr = (guint32) RANDOM(context, str->n_aux_blocks_needed);
if (g_array_index(str->aux_blocks, guint *, aux_block_nr) == NULL) {
- g_array_index(str->aux_blocks, guint8 *, aux_block_nr) = (guint8 *) strdup(g_array_index(str->blocks, gchar *, tmp));
+ ALLOC_COPY8(g_array_index(str->aux_blocks, guint8 *, aux_block_nr),
+ g_array_index(str->blocks, gchar *, tmp),
+ str->n_chars_in_block);
} else {
oneliner_string_xor(g_array_index(str->aux_blocks, guint8 *, aux_block_nr),
g_array_index(str->blocks, guint8 *, tmp),
@@ -472,17 +495,190 @@
chunk);
}
+static guint8 *
+oneliner_superstring_get_combined_block(oneliner_superstring *str, guint32 block_nr)
+{
+ if (block_nr < str->blocks->len)
+ return g_array_index(str->blocks, guint8 *, block_nr);
+ else
+ return g_array_index(str->aux_blocks, guint8 *, block_nr - str->blocks->len);
+}
+
static void
+oneliner_superstring_set_combined_block(oneliner_superstring *str, guint32 block_nr, guint8 *block)
+{
+ if (block_nr < str->blocks->len)
+ g_array_index(str->blocks, guint8 *, block_nr) = block;
+ else
+ g_array_index(str->aux_blocks, guint8 *, block_nr - str->blocks->len) = block;
+}
+
+static oneliner_xor_block *
+oneliner_xor_block_new(guint8 *data, guint32 len)
+{
+ oneliner_xor_block *rval = g_new0(oneliner_xor_block, 1);
+ ALLOC_COPY8(rval->sum, data, len);
+ rval->source_blocks = g_hash_table_new(g_int_hash, g_int_equal);
+}
+
+static gboolean
+oneliner_xor_block_free_and_remove(gpointer key, gpointer data, gpointer user_data)
+{
+ g_free(key);
+ g_free(data);
+ return TRUE;
+}
+
+static void
+oneliner_xor_block_free(oneliner_xor_block *xor_block)
+{
+ g_free(xor_block->sum);
+ g_hash_table_foreach_remove(xor_block->source_blocks, oneliner_xor_block_free_and_remove, NULL);
+ g_hash_table_destroy(xor_block->source_blocks);
+ g_free(xor_block);
+}
+
+static void
+oneliner_xor_block_add(oneliner_xor_block *xor_block, guint32 source_block_nr)
+{
+ guint32 *uses;
+ guint32 *source;
+ if ((uses = g_hash_table_lookup(xor_block->source_blocks, &source_block_nr)) != NULL) {
+ (*uses)++;
+ } else {
+ uses = g_new(guint32, 1);
+ source = g_new(guint32, 1);
+ *uses = 1;
+ *source = source_block_nr;
+ g_hash_table_insert(xor_block->source_blocks, source, uses);
+ }
+}
+
+static void
+oneliner_xor_block_last_source_block_iterator(gpointer key, gpointer data, gpointer user_data)
+{
+ * (guint32 *) user_data = * (guint32 *) key;
+}
+
+static guint32
+oneliner_xor_block_last_source_block(oneliner_xor_block *xor_block)
+{
+ guint32 source_block_nr;
+ g_hash_table_foreach(xor_block->source_blocks, oneliner_xor_block_last_source_block_iterator, &source_block_nr);
+ return source_block_nr;
+}
+
+static void
+oneliner_xor_block_last_uses_iterator(gpointer key, gpointer data, gpointer user_data)
+{
+ * (guint32 *) user_data = * (guint32 *) data;
+}
+
+static guint32
+oneliner_xor_block_last_uses(oneliner_xor_block *xor_block)
+{
+ guint32 uses;
+ g_hash_table_foreach(xor_block->source_blocks, oneliner_xor_block_last_uses_iterator, &uses);
+ return uses;
+}
+
+static gboolean
+oneliner_xor_block_finished(oneliner_xor_block *xor_block)
+{
+ if ((g_hash_table_size(xor_block->source_blocks) == 1) &&
+ ((oneliner_xor_block_last_uses(xor_block) % 2) == 1))
+ return TRUE;
+ else
+ return FALSE;
+}
+
+static oneliner_graph_insertion *
+oneliner_graph_insertion_new(oneliner_xor_block *check_block, guint32 source_block_nr)
+{
+ oneliner_graph_insertion *rval = g_new0(oneliner_graph_insertion, 1);
+ rval->check_block = check_block;
+ rval->source_block_nr = source_block_nr;
+ return rval;
+}
+
+static void
+oneliner_graph_insertion_free_with_cb(gpointer insertion, gpointer user_data)
+{
+ oneliner_xor_block_free(( (oneliner_graph_insertion *) insertion )->check_block);
+ g_free(insertion);
+}
+
+static void
+oneliner_insertion_execute(gpointer insertion, gpointer string)
+{
+ oneliner_graph_insertion *ins = (oneliner_graph_insertion *) insertion;
+ oneliner_superstring *str = (oneliner_superstring *) string;
+ guint32 *source_block_nr = g_new(guint32, 1);
+ GList *check_blocks = g_hash_table_lookup(str->graph, &(ins->source_block_nr));
+
+ *source_block_nr = ins->source_block_nr;
+ check_blocks = g_list_append(check_blocks, ins->check_block);
+ g_hash_table_insert(str->graph, source_block_nr, check_blocks);
+
+ g_free(insertion);
+}
+
+static void
oneliner_superstring_add_to_graph(oneliner_superstring *str, guint32 seed, guint8 *chunk, guint32 chunk_len)
{
oneliner_context *context = oneliner_context_new();
GArray *content_blocks;
+ guint32 tmp;
oneliner_context_seed(context, (gint32) seed);
content_blocks = oneliner_superstring_get_blocks_from_chunk(str, chunk, chunk_len);
- g_free(content_blocks);
+ for (tmp = 0; tmp < content_blocks->len; tmp++) {
+ guint32 degree = oneliner_context_get_degree(context);
+ if (degree == 1) {
+ guint32 block_nr = RANDOM(context, str->blocks->len + str->aux_blocks->len);
+ oneliner_superstring_set_combined_block(str, block_nr, g_array_index(content_blocks, guint8 *, tmp));
+ oneliner_superstring_analyze(block_nr);
+ } else {
+ GList *inserts = NULL;
+ guint32 unknown_source_blocks = 0;
+ guint32 unknown_source_block_nr = 0;
+ guint32 tmp2;
+ oneliner_xor_block *xor_block = oneliner_xor_block_new(g_array_index(content_blocks, guint8 *, tmp),
+ str->n_chars_in_block);
+
+ for (tmp2 = 0; tmp2 < degree; tmp2++) {
+ guint32 block_nr = RANDOM(context, str->blocks->len + str->aux_blocks->len);
+ guint8 *block_content = oneliner_superstring_get_combined_block(str, block_nr);
+ if (block_content != NULL) {
+ oneliner_string_xor(xor_block->sum, block_content, str->n_chars_in_block);
+ } else {
+ oneliner_xor_block_add(xor_block, block_nr);
+ inserts = g_list_append(inserts, oneliner_graph_insertion_new(xor_block, block_nr));
+ unknown_source_blocks++;
+ unknown_source_block_nr = block_nr;
+ }
+ }
+
+ if (oneliner_xor_block_finished(xor_block)) {
+ gboolean free_check_block = TRUE;
+
+ oneliner_superstring_set_combined_block(str, unknown_source_block_nr, xor_block->sum);
+
+ g_list_foreach(inserts, oneliner_graph_insertion_free_with_cb, &free_check_block);
+ g_list_free(inserts);
+
+ oneliner_superstring_analyze(unknown_source_block_nr);
+ } else {
+ g_list_foreach(inserts, oneliner_insertion_execute, str);
+ g_list_free(inserts);
+ }
+
+ }
+ }
+
+ g_array_free(content_blocks, TRUE);
g_free(context);
}
@@ -516,6 +712,7 @@
g_array_set_size(str->blocks, str->n_blocks_needed);
str->aux_blocks = g_array_new(FALSE, TRUE, sizeof(guint8 *));
g_array_set_size(str->aux_blocks, str->n_aux_blocks_needed);
+ str->graph = g_hash_table_new(g_int_hash, g_int_equal);
}
oneliner_superstring_add_to_graph(str, seed, (guint8 *) RSTRING(chunk)->ptr + 8, (guint32) RSTRING(chunk)->len - 8);
@@ -524,22 +721,14 @@
}
static guint8 *
-oneliner_superstring_get_combined_block(oneliner_superstring *str, guint32 block_no)
-{
- if (block_no < str->blocks->len)
- return g_array_index(str->blocks, guint8 *, block_no);
- else
- return g_array_index(str->aux_blocks, guint8 *, block_no - str->blocks->len);
-}
-
-static guint8 *
oneliner_superstring_get_check_block(oneliner_superstring *str, oneliner_context *context)
{
guint32 degree = oneliner_context_get_degree(context);
guint32 block_nr = RANDOM(context, str->blocks->len + str->aux_blocks->len);
- guint8 *rval = (guint8 *) strdup((gchar *) oneliner_superstring_get_combined_block(str, block_nr));
+ guint8 *rval;
guint32 tmp;
+ ALLOC_COPY8(rval, oneliner_superstring_get_combined_block(str, block_nr), str->n_chars_in_block);
for (tmp = 2; tmp <= degree; tmp++)
oneliner_string_xor(rval,
oneliner_superstring_get_combined_block(str, RANDOM(context, str->blocks->len + str->aux_blocks->len)),
@@ -586,11 +775,32 @@
}
static void
+oneliner_superstring_free_and_remove_check_blocks(gpointer data, gpointer user_data)
+{
+ oneliner_xor_block_free((oneliner_xor_block *) data);
+}
+
+static gboolean
+oneliner_superstring_free_and_remove(gpointer source_block_nr, gpointer check_blocks, gpointer user_data)
+{
+ g_free(source_block_nr);
+ g_list_foreach((GList *) check_blocks, oneliner_superstring_free_and_remove_check_blocks, NULL);
+ g_list_free((GList *) check_blocks);
+ return TRUE;
+}
+
+static void
oneliner_superstring_free(oneliner_superstring *str)
{
guint32 tmp;
- g_array_free(str->blocks, TRUE);
- g_array_free(str->aux_blocks, TRUE);
+ if (str->blocks != NULL)
+ g_array_free(str->blocks, TRUE);
+ if (str->aux_blocks != NULL)
+ g_array_free(str->aux_blocks, TRUE);
+ if (str->graph != NULL) {
+ g_hash_table_foreach_remove(str->graph, oneliner_superstring_free_and_remove, NULL);
+ g_hash_table_destroy(str->graph);
+ }
g_free(str);
}
Modified: trunk/oneliner/tests/superstring_test.rb
===================================================================
--- trunk/oneliner/tests/superstring_test.rb 2007-05-19 22:04:14 UTC (rev 277)
+++ trunk/oneliner/tests/superstring_test.rb 2007-05-21 09:46:16 UTC (rev 278)
@@ -3,6 +3,13 @@
class SuperStringTest < Test::Unit::TestCase
+ def test_encode_size
+ s = Oneliner::SuperString.new("hehu")
+ 8.upto(20) do |n|
+ assert_equal((n - 8) * 8, s.chunk_blocks(s.encode(n)).size)
+ end
+ end
+
def test_blocks
8.times do |m|
n = 128 * m + 63
More information about the Archipelago-submits
mailing list