[Archipelago-submits] [281] trunk/oneliner: removed useless stuff
nobody at rubyforge.org
nobody at rubyforge.org
Mon May 21 14:28:34 EDT 2007
Revision: 281
Author: zond
Date: 2007-05-21 14:28:34 -0400 (Mon, 21 May 2007)
Log Message:
-----------
removed useless stuff
Modified Paths:
--------------
trunk/oneliner/ext/extconf.rb
Added Paths:
-----------
trunk/oneliner/ext/oneliner.c
Removed Paths:
-------------
trunk/oneliner/ext/oneliner_ext.c
trunk/oneliner/lib/
Modified: trunk/oneliner/ext/extconf.rb
===================================================================
--- trunk/oneliner/ext/extconf.rb 2007-05-21 18:21:42 UTC (rev 280)
+++ trunk/oneliner/ext/extconf.rb 2007-05-21 18:28:34 UTC (rev 281)
@@ -43,4 +43,4 @@
$CFLAGS += " -g -gdwarf-2 -g3 " + `pkg-config --cflags --libs glib-2.0`.strip
-create_makefile("oneliner_ext")
+create_makefile("oneliner")
Copied: trunk/oneliner/ext/oneliner.c (from rev 280, trunk/oneliner/ext/oneliner_ext.c)
===================================================================
--- trunk/oneliner/ext/oneliner.c (rev 0)
+++ trunk/oneliner/ext/oneliner.c 2007-05-21 18:28:34 UTC (rev 281)
@@ -0,0 +1,908 @@
+// Archipelago - a distributed computing toolkit for ruby
+// Copyright (C) 2006 Martin Kihlgren <zond at troja dot ath dot cx>
+//
+// 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 "ruby.h"
+#include <limits.h>
+#include <openssl/aes.h>
+#include <glib.h>
+#include <stdlib.h>
+#include <math.h>
+
+//
+// The classes
+//
+static VALUE rb_superstring;
+
+//
+// Utility macros.
+//
+#ifdef ONELINER_DEBUG
+#define DEBUG(s, ...) { \
+ fprintf(stderr, "DEBUG: "); \
+ fprintf(stderr, s, ## __VA_ARGS__); \
+ fprintf(stderr, "\n"); \
+ fflush(NULL); }
+#define IFDEBUG(s) s
+#define BITSTRING_DEBUG(msg,str,len) { \
+ fprintf(stderr, "DEBUG: %s: ", (msg)); \
+ rb_funcall(rb_const_get(rb_cObject, rb_intern("Kernel")), \
+ rb_intern("print"), \
+ 1, \
+ rb_funcall(rb_funcall(rb_funcall(rb_str_new((gchar *) (str), (len)), \
+ rb_intern("unpack"), \
+ 1, \
+ rb_str_new2("b*")), \
+ rb_intern("first"), \
+ 0), \
+ rb_intern("gsub"), \
+ 2, \
+ rb_funcall(rb_const_get(rb_cObject, rb_intern("Regexp")), \
+ rb_intern("new"), \
+ 1, \
+ rb_str_new2("(.{4,4})")), \
+ rb_str_new2("\\1,"))); \
+ fprintf(stderr, "\n"); \
+ fflush(NULL); }
+#define STRING_DEBUG(msg,str,len) { \
+ fprintf(stderr, "DEBUG: %s: ", (msg)); \
+ rb_funcall(rb_const_get(rb_cObject, rb_intern("Kernel")), rb_intern("print"), 1, rb_funcall(rb_str_new((gchar *) (str), (len)), rb_intern("inspect"), 0)); \
+ fprintf(stderr, "\n"); \
+ fflush(NULL); }
+#else
+#define DEBUG(s, ...) ;
+#define IFDEBUG(s) ;
+#define BITSTRING_DEBUG(msg,str,len) ;
+#endif
+
+#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
+
+//
+// The c representation of a superstring.
+//
+typedef struct {
+ // The blocks of this superstring.
+ GArray *blocks;
+ // The aux blocks of this superstring.
+ GArray *aux_blocks;
+ // Our graph of check blocks.
+ GArray *graph;
+ // Our graph of aux blocks for the source blocks.
+ GArray *aux_graph_for_source_blocks;
+ // Our graph of aux blocks for the aux blocks themselves.
+ GArray *aux_graph_for_aux_blocks;
+ // The size of each block in bits.
+ guint32 block_size;
+ // The number of guint8's needed to contain those bits.
+ guint32 n_chars_in_block;
+ // The length of the original data.
+ guint32 data_len;
+ // The number of blocks needed to contain that data.
+ guint32 n_blocks_needed;
+ // The number of bytes needed to store those blocks.
+ guint32 n_bytes_for_blocks;
+ // The number of aux blocks needed for those blocks.
+ guint32 n_aux_blocks_needed;
+ // The number of check blocks we have decoded so far.
+ guint32 n_known_check_blocks;
+ // Whether we have decided already that we are done decoding.
+ gboolean decode_done;
+} oneliner_superstring;
+
+//
+// A random context.
+//
+typedef guint8 oneliner_context;
+
+static guint8 *
+oneliner_superstring_get_combined_block(oneliner_superstring *str, guint32 block_nr);
+static void
+oneliner_superstring_analyze(oneliner_superstring *str, guint32 found_block_nr);
+
+#include "context.c"
+#include "string.c"
+#include "xor_block.c"
+#include "graph_insertion.c"
+
+//
+// Return the block size in bits for a string of the given length.
+//
+static guint32
+oneliner_superstring_get_block_size(guint32 len) {
+ if (len < 1024) {
+ return (guint32) ceil((len / 1024.0) * 8.0);
+ } else {
+ return ((len / 128) / 8) * 8;
+ }
+}
+
+//
+// Fill *block with a block_size (bitwise) piece of *data from pos (bitwise).
+//
+static void
+oneliner_superstring_get_block_from_data(guint8 *data, guint32 pos, guint32 block_size, guint8 *block)
+{
+ //
+ // Block sizes 1-7 are tricky,
+ // but all other sizes are divisible by 8 and therefore ok to do with a simple memcpy.
+ //
+ if (block_size < 8) {
+ // If the whole block fits within one char then we cant assume that we have permission
+ // to read the char after it, but if it DOESNT then we MUST assume that we have permission
+ // to read the char after it. Therefore the below fork where we read a char or a short from the data.
+ if ((pos + block_size - 1) / 8 == pos / 8) {
+ *block = data[pos / 8];
+ *block = *block << (8 - ((pos + block_size) % 8)) % 8;
+ *block = *block >> 8 - block_size;
+ } else {
+ guint16 short_containing_block = * (guint16 *) (data + (pos / 8));
+ short_containing_block = short_containing_block << (8 - ((pos + block_size) % 8)) % 8;
+ short_containing_block = short_containing_block >> 16 - block_size;
+ *block = (guint8) short_containing_block;
+ }
+ } else {
+ memcpy(block, data + (pos / 8), sizeof(guint8) * (block_size / 8));
+ }
+}
+
+//
+// Take *data and return a GArray * with all the block_size blocks it contains.
+// Needs hints as to how many bytes we need to contain all blocks, how long *data is,
+// how many chars each block needs and how many blocks we need in total.
+//
+static GArray *
+oneliner_superstring_build_blocks_from_data(guint32 n_bytes_for_blocks,
+ guint32 data_len,
+ guint32 block_size,
+ guint32 n_chars_in_block,
+ guint32 n_blocks_needed,
+ guint8 *data)
+{
+ 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_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_nr) = tmp_block;
+ }
+
+ return rval;
+}
+
+
+//
+// Ensure that str->blocks contains a GArray with all the blocks of this data.
+//
+static void
+oneliner_superstring_build_blocks(oneliner_superstring *str, guint8 *data)
+{
+ str->blocks = oneliner_superstring_build_blocks_from_data(str->n_bytes_for_blocks,
+ str->data_len,
+ str->block_size,
+ str->n_chars_in_block,
+ str->n_blocks_needed,
+ data);
+}
+
+//
+// Take the block_size (bitwise) content of *block and insert it in *data at block_nr.
+//
+static void
+oneliner_superstring_set_data_from_block(guint8 *data, guint32 block_nr, guint32 block_size, guint8 *block)
+{
+ //
+ // If the block size is less than 8 then we have some tricky business, otherwise
+ // we know that it is a multiple of 8, which makes it into a simple memcpy.
+ //
+ if (block_size < 8) {
+ // If the entire block fits within one byte then we can not assume that we can write
+ // the byte after, but if it doesnt then we MUST assume that we CAN write the byte
+ // after, therefore the below fork where we write a char or a long depending.
+ if ((block_nr * block_size) / 8 == (((block_nr + 1) * block_size) - 1) / 8) {
+ // Set the byte we want to write to the block content.
+ guint8 byte_to_write = *block;
+ // Left shift it enough so that it matches the segment of data we want to write.
+ byte_to_write = byte_to_write << (block_nr * block_size) % 8;
+ // Then OR the corresponding byte in the data with the byte to write. Since
+ // the data is supposed to be initialized with zeroes this ought to do the trick.
+ data[(block_nr * block_size) / 8] = data[(block_nr * block_size) / 8] | byte_to_write;
+ } else {
+ // Set the short we want to write to the block content.
+ guint16 short_to_write = (guint16) *block;
+ // Left shift it enough so that it matches the segment of data we want to write.
+ short_to_write = short_to_write << (block_nr * block_size) % 8;
+ // Then OR the corresponding short in the data with the short to write. Since
+ // the data is supposed to be initialized with zeroes this ought to do the trick.
+ * (guint16 *) (data + (block_nr * block_size) / 8) = * (guint16 *) (data + (block_nr * block_size) / 8) | short_to_write;
+ }
+ } else {
+ memcpy((gchar *) data + (block_nr * (block_size / 8)), (gchar *) block, sizeof(guint8) * (block_size / 8));
+ }
+}
+
+//
+// Take the given blocks of size block_size needing n_bytes_for_blocks to be stored completely and
+// concatenate them into a string, then return the first data_len bytes of the result.
+//
+// If prepend_size is larger than 0 then the prepend string will be prepended to the result.
+//
+static guint8 *
+oneliner_superstring_build_data_from_blocks(guint32 n_bytes_for_blocks,
+ guint32 data_len,
+ guint32 block_size,
+ GArray *blocks,
+ guint32 prepend_size,
+ guint8 *prepend)
+{
+ guint32 index;
+ guint8 *tmp_data = g_new0(guint8, n_bytes_for_blocks + prepend_size + 1);
+ for (index = 0; index < blocks->len; index++) {
+ oneliner_superstring_set_data_from_block(tmp_data + prepend_size, index, block_size, g_array_index(blocks, guint8 *, index));
+ }
+ memcpy((gchar *) tmp_data, (gchar *) prepend, sizeof(guint8) * prepend_size);
+ return g_realloc(tmp_data, data_len);
+}
+
+//
+// Return the guint8 * that the given *str describes with its blocks.
+//
+static guint8 *
+oneliner_superstring_build_data(oneliner_superstring *str)
+{
+ return oneliner_superstring_build_data_from_blocks(str->n_bytes_for_blocks,
+ str->data_len,
+ str->block_size,
+ str->blocks,
+ 0,
+ NULL);
+}
+
+//
+// Create the aux_blocks GArray for *str using its blocks and length.
+//
+static void
+oneliner_superstring_build_aux_blocks(oneliner_superstring *str)
+{
+ guint32 tmp;
+ oneliner_context *context = oneliner_context_new();
+
+ oneliner_context_seed(context, (gint32) str->data_len);
+ str->aux_blocks = g_array_new(FALSE, TRUE, sizeof(guint8 *));
+ g_array_set_size(str->aux_blocks, str->n_aux_blocks_needed);
+
+ for (tmp = 0; tmp < str->n_blocks_needed; tmp++) {
+ guint32 tmp2;
+ for (tmp2 = 0; tmp2 < Q; tmp2++) {
+ guint32 aux_block_nr = (guint32) RANDOM(context, str->n_aux_blocks_needed);
+ if (g_array_index(str->aux_blocks, guint *, aux_block_nr) == NULL) {
+ 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),
+ str->n_chars_in_block);
+ }
+ }
+ }
+
+ g_free(context);
+}
+
+//
+// Initialize all the precalculated state of *str using data_len.
+//
+static void
+oneliner_superstring_initialize(oneliner_superstring *str, guint32 data_len)
+{
+ // Make sure the length of our data (our String superclass content) is set.
+ str->data_len = (guint32) data_len;
+ // Make sure the block size we deem reasonable for this data length is set.
+ str->block_size = oneliner_superstring_get_block_size(str->data_len);
+ // Make sure the number of chars needed to contain such a block is set.
+ str->n_chars_in_block = (guint32) ceil(str->block_size / 8.0);
+ // Make sure the number of blocks needed to contain this data is set.
+ str->n_blocks_needed = (guint32) ceil((str->data_len * 8.0) / str->block_size);
+ // Make sure the number of bytes needed to contain those blocks is set.
+ str->n_bytes_for_blocks = (guint32) ceil((str->n_blocks_needed * str->block_size) / 8.0);
+ // Make sure the number of aux blocks needed for those blocks is set.
+ str->n_aux_blocks_needed = (guint32) ceil(0.55 * Q * E * str->n_blocks_needed);
+ // Make sure the number of known check blocks so far is set.
+ str->n_known_check_blocks = 0;
+ // Make sure we dont think we have decoded already.
+ str->decode_done = FALSE;
+}
+
+//
+// Initialize a superstring using (possibly) a String to encode.
+//
+static VALUE
+rb_oneliner_superstring_initialize(int argc, VALUE *argv, VALUE self)
+{
+ oneliner_superstring *str;
+
+ if (argc > 1) {
+ rb_raise(rb_eRuntimeError, "Oneliner::SuperString.new(String s = nil) takes at most 1 argument.");
+ } else if (argc == 1) {
+ Check_Type(argv[0], T_STRING);
+
+ if (RSTRING(argv[0])->len < 1)
+ rb_raise(rb_eRuntimeError, "First argument to Oneliner::SuperString.new(String s = nil) must be a String of at least size 1 if given.");
+
+ RB_ONELINER(self, str);
+
+ oneliner_superstring_initialize(str, RSTRING(argv[0])->len);
+
+ // Make sure that we have our blocks calculated properly.
+ oneliner_superstring_build_blocks(str, (guint8 *) RSTRING(argv[0])->ptr);
+ oneliner_superstring_build_aux_blocks(str);
+ }
+ return self;
+}
+
+//
+// Returns whether *str is done decoding.
+//
+static VALUE
+oneliner_superstring_decode_done(oneliner_superstring *str)
+{
+ guint32 tmp;
+ if (str->decode_done)
+ return Qtrue;
+ if (str->blocks == NULL)
+ return Qfalse;
+ if (str->n_known_check_blocks < str->n_blocks_needed)
+ return Qfalse;
+ for (tmp = 0; tmp < str->n_blocks_needed; tmp++)
+ if (g_array_index(str->blocks, guint8 *, tmp) == NULL)
+ return Qfalse;
+ str->decode_done = TRUE;
+ return Qtrue;
+}
+
+//
+// Returns a GArray * containing all the blocks described by *chunk of length chunk_len
+// in the context of *str (its block_size, n_chars_in_block etc).
+//
+static GArray *
+oneliner_superstring_get_blocks_from_chunk(oneliner_superstring *str, guint8 *chunk, guint32 chunk_len)
+{
+ return oneliner_superstring_build_blocks_from_data(chunk_len,
+ chunk_len,
+ str->block_size,
+ str->n_chars_in_block,
+ (chunk_len * 8) / str->block_size,
+ chunk);
+}
+
+//
+// Return the guint8 * at either source or aux block with index block_nr in *str.
+//
+static guint8 *
+oneliner_superstring_get_combined_block(oneliner_superstring *str, guint32 block_nr)
+{
+ if (block_nr < str->n_blocks_needed)
+ return g_array_index(str->blocks, guint8 *, block_nr);
+ else
+ return g_array_index(str->aux_blocks, guint8 *, block_nr - str->n_blocks_needed);
+}
+
+//
+// Set either the source of aux block at block_nr of *str to *block.
+//
+static void
+oneliner_superstring_set_combined_block(oneliner_superstring *str, guint32 block_nr, guint8 *block)
+{
+ if (block_nr < str->n_blocks_needed && g_array_index(str->blocks, guint8 *, block_nr) == NULL) {
+ ALLOC_COPY8(g_array_index(str->blocks, guint8 *, block_nr), block, str->n_chars_in_block);
+ } else if (g_array_index(str->aux_blocks, guint8 *, block_nr - str->n_blocks_needed) == NULL) {
+ ALLOC_COPY8(g_array_index(str->aux_blocks, guint8 *, block_nr - str->n_blocks_needed), block, str->n_chars_in_block);
+ }
+}
+
+static void
+oneliner_superstring_analyze_source_block_with_array(oneliner_superstring *str,
+ GArray *ary,
+ guint32 found_block_nr)
+{
+ guint32 source_block_nr;
+ GList *list_element;
+ GList *list_head = g_array_index(ary, GList *, found_block_nr);
+ oneliner_xor_block *xor_block;
+
+ // For each xor_block-containing item in the list.
+ for (list_element = list_head; list_element != NULL; list_element = g_list_next(list_element)) {
+ // Fetch its xor_block
+ xor_block = (oneliner_xor_block *) list_element->data;
+
+ // Apply this new knowledge to it.
+ oneliner_xor_block_apply(xor_block,
+ str,
+ found_block_nr);
+
+ //
+ // If that meant that it is finished then dance the dance of setting the combined block,
+ // freeing the check block, removing it from the GList of check blocks for that combined block,
+ // and analyzing the results.
+ //
+ // Otherwise if it is empty, just free it and remove it.
+ //
+ if (XOR_BLOCK_FINISHED(xor_block)) {
+
+ // Find the source block that it defines.
+ source_block_nr = oneliner_xor_block_last_source_block_nr(xor_block);
+
+ // And set it.
+ oneliner_superstring_set_combined_block(str,
+ source_block_nr,
+ xor_block->sum);
+ // Then free the check block.
+ oneliner_xor_block_free(xor_block);
+
+ // Then remove it from our unresolved check blocks so that we can run analyze safely again.
+ g_array_index(ary, GList *, found_block_nr) = g_list_remove_link(list_head, list_element);
+
+ // Then remove the list element that contained this check block.
+ g_list_free_1(list_element);
+
+ // And now analyze what the newly found source block led to.
+ // (Right, it can be an aux block as well, but my logic is still correct, I believe.)
+ oneliner_superstring_analyze(str, source_block_nr);
+ } else if (XOR_BLOCK_EMPTY(xor_block)) {
+ // Free the check block.
+ oneliner_xor_block_free(xor_block);
+ // Remove it from our unresolved list.
+ g_array_index(ary, GList *, found_block_nr) = g_list_remove_link(list_head, list_element);
+ // And remove the list element.
+ g_list_free_1(list_element);
+ }
+ }
+}
+
+static void
+oneliner_superstring_analyze_source_block(oneliner_superstring *str, guint32 found_block_nr)
+{
+ oneliner_superstring_analyze_source_block_with_array(str,
+ str->graph,
+ found_block_nr);
+
+ oneliner_superstring_analyze_source_block_with_array(str,
+ str->aux_graph_for_source_blocks,
+ found_block_nr);
+}
+
+static void
+oneliner_superstring_analyze_aux_block(oneliner_superstring *str, guint32 found_block_nr)
+{
+ oneliner_xor_block *xor_block;
+
+ if ((xor_block = g_array_index(str->aux_graph_for_aux_blocks,
+ oneliner_xor_block *,
+ found_block_nr - str->n_blocks_needed)) != NULL) {
+ oneliner_xor_block_set_sum(xor_block, oneliner_superstring_get_combined_block(str, found_block_nr), str->n_chars_in_block);
+ if (XOR_BLOCK_FINISHED(xor_block)) {
+ guint32 source_block_nr = oneliner_xor_block_last_source_block_nr(xor_block);
+
+ oneliner_superstring_set_combined_block(str,
+ source_block_nr,
+ xor_block->sum);
+ oneliner_xor_block_free(xor_block);
+
+ g_array_index(str->aux_graph_for_aux_blocks,
+ oneliner_xor_block *,
+ found_block_nr - str->n_blocks_needed) = NULL;
+
+ oneliner_superstring_analyze(str, source_block_nr);
+ } else if (XOR_BLOCK_EMPTY(xor_block)) {
+ oneliner_xor_block_free(xor_block);
+ g_array_index(str->aux_graph_for_aux_blocks,
+ oneliner_xor_block *,
+ found_block_nr - str->n_blocks_needed) = NULL;
+ }
+ }
+}
+
+static void
+oneliner_superstring_analyze(oneliner_superstring *str, guint32 found_block_nr)
+{
+ if (found_block_nr < str->n_blocks_needed) {
+ oneliner_superstring_analyze_source_block(str, found_block_nr);
+ } else {
+ oneliner_superstring_analyze_aux_block(str, found_block_nr);
+ }
+}
+
+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;
+ guint32 tmp2;
+ guint32 unknown_source_blocks;
+ guint32 unknown_source_block_nr;
+ GList *inserts;
+ oneliner_xor_block *xor_block;
+ guint32 degree;
+ guint32 block_nr;
+ guint8 *block_content;
+
+ oneliner_context_seed(context, (gint32) seed);
+
+ content_blocks = oneliner_superstring_get_blocks_from_chunk(str, chunk, chunk_len);
+
+ for (tmp = 0; tmp < content_blocks->len; tmp++) {
+ degree = oneliner_context_get_degree(context);
+ if (degree == 1) {
+ block_nr = RANDOM(context, str->n_blocks_needed + str->n_aux_blocks_needed);
+ oneliner_superstring_set_combined_block(str, block_nr, g_array_index(content_blocks, guint8 *, tmp));
+ oneliner_superstring_analyze(str, block_nr);
+ } else {
+ unknown_source_blocks = 0;
+ unknown_source_block_nr = 0;
+ inserts = NULL;
+
+ xor_block = oneliner_xor_block_new(g_array_index(content_blocks, guint8 *, tmp),
+ str->n_chars_in_block,
+ TRUE);
+
+ for (tmp2 = 0; tmp2 < degree; tmp2++) {
+ block_nr = RANDOM(context, str->n_blocks_needed + str->n_aux_blocks_needed);
+ 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 (XOR_BLOCK_FINISHED(xor_block)) {
+ oneliner_superstring_set_combined_block(str, unknown_source_block_nr, xor_block->sum);
+
+ g_list_foreach(inserts, oneliner_graph_insertion_free_with_check_block, NULL);
+ g_list_free(inserts);
+
+ oneliner_superstring_analyze(str, unknown_source_block_nr);
+ } else {
+ g_list_foreach(inserts, oneliner_insertion_execute, str);
+ g_list_free(inserts);
+ }
+
+ }
+ (str->n_known_check_blocks)++;
+ }
+
+ g_array_free(content_blocks, TRUE);
+ g_free(context);
+}
+
+static void
+oneliner_superstring_build_aux_graph(oneliner_superstring *str)
+{
+ oneliner_context *context = oneliner_context_new();
+ guint32 tmp;
+ guint8 *zeroes = g_new0(guint8, str->n_chars_in_block);
+ guint32 tmp2;
+ guint32 aux_block_nr;
+ oneliner_xor_block *aux_block;
+ GList *aux_blocks;
+
+ oneliner_context_seed(context, (gint32) str->data_len);
+ str->aux_graph_for_aux_blocks = g_array_new(FALSE, TRUE, sizeof(oneliner_xor_block *));
+ g_array_set_size(str->aux_graph_for_aux_blocks, str->n_aux_blocks_needed);
+ str->aux_graph_for_source_blocks = g_array_new(FALSE, TRUE, sizeof(GList *));
+ g_array_set_size(str->aux_graph_for_source_blocks, str->n_blocks_needed);
+
+ for (tmp = 0; tmp < str->n_blocks_needed; tmp++) {
+ aux_blocks = NULL;
+
+ for (tmp2 = 0; tmp2 < Q; tmp2++) {
+ aux_block_nr = RANDOM(context, str->n_aux_blocks_needed);
+
+ if ((aux_block = g_array_index(str->aux_graph_for_aux_blocks, oneliner_xor_block *, aux_block_nr)) == NULL) {
+ aux_block = oneliner_xor_block_new(zeroes, str->n_chars_in_block, FALSE);
+ g_array_index(str->aux_graph_for_aux_blocks, oneliner_xor_block *, aux_block_nr);
+ }
+
+ oneliner_xor_block_add(aux_block, tmp);
+ aux_blocks = g_list_append(aux_blocks, aux_block);
+ }
+
+ g_array_index(str->aux_graph_for_source_blocks, GList *, tmp) = aux_blocks;
+ }
+
+ g_free(zeroes);
+ g_free(context);
+}
+
+static VALUE
+rb_oneliner_superstring_decode(VALUE self, VALUE chunk)
+{
+ oneliner_superstring *str;
+ guint32 data_len;
+ guint32 seed;
+ guint32 blocks_needed;
+
+ Check_Type(chunk, T_STRING);
+
+ RB_ONELINER(self, str);
+
+ if (RSTRING(chunk)->len < 8)
+ rb_raise(rb_eRuntimeError, "Oneliner::SuperString#decode(String chunk) needs an argument that is at least 8 characters long.");
+
+ data_len = ((guint32 *) RSTRING(chunk)->ptr)[0];
+ seed = ((guint32 *) RSTRING(chunk)->ptr)[1];
+
+ if (str->data_len == 0) {
+ str->data_len = data_len;
+ } else if (str->data_len != data_len) {
+ rb_raise(rb_eRuntimeError, "Oneliner::Superstring#decode(String chunk) needs all consecutive calls to be with arguments having the same first four characters. Didn't you use chunks produced using #encode calls from the same instance?");
+ }
+
+ if (str->blocks == NULL) {
+ oneliner_superstring_initialize(str, data_len);
+ str->blocks = g_array_new(FALSE, TRUE, sizeof(guint8 *));
+ 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_array_new(FALSE, TRUE, sizeof(GList *));
+ oneliner_superstring_build_aux_graph(str);
+ }
+
+ oneliner_superstring_add_to_graph(str, seed, (guint8 *) RSTRING(chunk)->ptr + 8, (guint32) RSTRING(chunk)->len - 8);
+
+ return oneliner_superstring_decode_done(str);
+}
+
+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->n_blocks_needed + str->n_aux_blocks_needed);
+ 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->n_blocks_needed + str->n_aux_blocks_needed)),
+ str->n_chars_in_block);
+
+ return rval;
+}
+
+static guint32
+oneliner_superstring_encode(oneliner_superstring *str, guint8 **buffer, guint32 len)
+{
+ oneliner_context *context = oneliner_context_new();
+ GArray *rval_ary = g_array_new(FALSE, FALSE, sizeof(guint8 *));
+ guint8 prepend[8];
+ gint32 tmp;
+
+ sranddev();
+ tmp = (gint32) rand();
+ oneliner_context_seed(context, tmp);
+
+ ( (guint32 *) prepend )[0] = str->data_len;
+ ( (guint32 *) prepend )[1] = (guint32) tmp;
+
+ while ((rval_ary->len * str->block_size) / 8 < len) {
+ guint8 *check_block = oneliner_superstring_get_check_block(str, context);
+ g_array_append_val(rval_ary, check_block);
+ }
+
+ // Here I let tmp describe the number of bytes needed to contain the rval_ary considering the block
+ // size. And since we cant really truncate it at the end at this stage (like we can in the final build_data_from_blocks)
+ // the data_len argument is the same as the n_bytes_for_blocks argument. Also, we want to prepend the original data-len
+ // and seed, so we use the prepend argument.
+ tmp = (guint32) ceil((rval_ary->len * str->block_size) / 8);
+ *buffer = oneliner_superstring_build_data_from_blocks(tmp,
+ tmp,
+ str->block_size,
+ rval_ary,
+ 8,
+ prepend);
+ g_free(context);
+ g_array_free(rval_ary, TRUE);
+
+ return tmp;
+}
+
+static void
+oneliner_superstring_free_xor_block(gpointer xor_block, gpointer user_data)
+{
+ oneliner_xor_block_free((oneliner_xor_block *) xor_block);
+}
+
+static void
+oneliner_superstring_free_ary_of_glists_of_xor_blocks(GArray *ary, gboolean free_xor_blocks)
+{
+ guint32 tmp;
+ for (tmp = 0; tmp < ary->len; tmp++) {
+ GList *list;
+ if ((list = (GList *) g_array_index(ary, GList *, tmp)) != NULL) {
+ if (free_xor_blocks)
+ g_list_foreach(list, oneliner_superstring_free_xor_block, NULL);
+ g_list_free(list);
+ }
+ }
+ g_array_free(ary, FALSE);
+}
+
+static void
+oneliner_superstring_free(oneliner_superstring *str)
+{
+ guint32 tmp;
+ 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)
+ oneliner_superstring_free_ary_of_glists_of_xor_blocks(str->graph, TRUE);
+ if (str->aux_graph_for_aux_blocks != NULL) {
+ for (tmp = 0; tmp < str->n_aux_blocks_needed; tmp++)
+ oneliner_xor_block_free((oneliner_xor_block *) g_array_index(str->aux_graph_for_aux_blocks, oneliner_xor_block *, tmp));
+ }
+ if (str->aux_graph_for_source_blocks != NULL)
+ oneliner_superstring_free_ary_of_glists_of_xor_blocks(str->aux_graph_for_source_blocks, FALSE);
+
+ g_free(str);
+}
+
+static VALUE
+rb_oneliner_superstring_alloc(VALUE klass)
+{
+ oneliner_superstring *str = g_new0(oneliner_superstring, 1);
+ return Data_Wrap_Struct(klass, NULL, oneliner_superstring_free, str);
+}
+
+static VALUE
+oneliner_superstring_get_blocks(GArray *container, guint32 len)
+{
+ guint32 tmp;
+ VALUE rval = rb_ary_new();
+ for (tmp = 0; tmp < container->len; tmp++) {
+ guint8 *tmp_block = g_array_index(container, guint8 *, tmp);
+ rb_ary_push(rval, rb_str_new((gchar *) tmp_block, len));
+ }
+ return rval;
+}
+
+static VALUE
+rb_oneliner_superstring_blocks(VALUE self)
+{
+ oneliner_superstring *str;
+ RB_ONELINER(self, str);
+ return oneliner_superstring_get_blocks(str->blocks, str->n_chars_in_block);
+}
+
+static VALUE
+rb_oneliner_superstring_aux_blocks(VALUE self)
+{
+ oneliner_superstring *str;
+ RB_ONELINER(self, str);
+ return oneliner_superstring_get_blocks(str->aux_blocks, str->n_chars_in_block);
+}
+
+static VALUE
+rb_oneliner_superstring_to_s(VALUE self)
+{
+ oneliner_superstring *str;
+ VALUE rval;
+ guint8 *tmp_data;
+
+ RB_ONELINER(self, str);
+ if (str->blocks == NULL)
+ return rb_str_new2("");
+ tmp_data = oneliner_superstring_build_data(str);
+ rval = rb_str_new((gchar *) tmp_data, str->data_len);
+ g_free(tmp_data);
+ return rval;
+}
+
+static VALUE
+rb_oneliner_superstring_block_size(VALUE self)
+{
+ oneliner_superstring *str;
+ RB_ONELINER(self, str);
+ return INT2NUM(str->block_size);
+}
+
+static VALUE
+rb_oneliner_superstring_encode(VALUE self, VALUE size)
+{
+ guint8 *chunk;
+ VALUE rval;
+ oneliner_superstring *str;
+ guint32 chunk_size;
+
+ Check_Type(size, T_FIXNUM);
+ if (NUM2INT(size) < 8)
+ rb_raise(rb_eRuntimeError, "Oneliner::SuperString#encode(Fixnum size) needs a size of at least 8.");
+
+ RB_ONELINER(self, str);
+
+ chunk_size = oneliner_superstring_encode(str, &chunk, NUM2INT(size));
+ rval = rb_str_new((gchar *) chunk, chunk_size);
+
+ g_free(chunk);
+
+ return rval;
+}
+
+static VALUE
+rb_oneliner_superstring_chunk_blocks(VALUE self, VALUE chunk)
+{
+ oneliner_superstring *str;
+ VALUE rval;
+ GArray *blocks;
+
+ Check_Type(chunk, T_STRING);
+
+ if (RSTRING(chunk)->len < 8)
+ rb_raise(rb_eRuntimeError, "Oneliner::SuperString.chunk_blocks(String chunk) needs an argument that is at least 8 characters long.");
+
+ RB_ONELINER(self, str);
+ blocks = oneliner_superstring_get_blocks_from_chunk(str,
+ (guint8 *) RSTRING(chunk)->ptr + 8,
+ (guint32) RSTRING(chunk)->len - 8);
+ rval = oneliner_superstring_get_blocks(blocks,
+ str->n_chars_in_block);
+ g_array_free(blocks, TRUE);
+ return rval;
+}
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+ void Init_oneliner_ext() {
+ VALUE rb_string = rb_define_class("String", rb_cObject);
+ rb_define_method(rb_string, "xor!", rb_oneliner_string_xor, 1);
+
+ rb_superstring = rb_define_class_under(rb_define_module("Oneliner"),
+ "SuperString",
+ rb_cObject);
+ rb_define_alloc_func(rb_superstring, rb_oneliner_superstring_alloc);
+ rb_define_method(rb_superstring, "initialize", rb_oneliner_superstring_initialize, -1);
+ rb_define_method(rb_superstring, "blocks", rb_oneliner_superstring_blocks, 0);
+ rb_define_method(rb_superstring, "aux_blocks", rb_oneliner_superstring_aux_blocks, 0);
+ rb_define_method(rb_superstring, "to_s", rb_oneliner_superstring_to_s, 0);
+ rb_define_method(rb_superstring, "encode", rb_oneliner_superstring_encode, 1);
+ rb_define_method(rb_superstring, "block_size", rb_oneliner_superstring_block_size, 0);
+ rb_define_method(rb_superstring, "chunk_blocks", rb_oneliner_superstring_chunk_blocks, 1);
+ rb_define_method(rb_superstring, "decode", rb_oneliner_superstring_decode, 1);
+ }
+#ifdef __cplusplus
+}
+#endif
+
Deleted: trunk/oneliner/ext/oneliner_ext.c
===================================================================
--- trunk/oneliner/ext/oneliner_ext.c 2007-05-21 18:21:42 UTC (rev 280)
+++ trunk/oneliner/ext/oneliner_ext.c 2007-05-21 18:28:34 UTC (rev 281)
@@ -1,908 +0,0 @@
-// Archipelago - a distributed computing toolkit for ruby
-// Copyright (C) 2006 Martin Kihlgren <zond at troja dot ath dot cx>
-//
-// 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 "ruby.h"
-#include <limits.h>
-#include <openssl/aes.h>
-#include <glib.h>
-#include <stdlib.h>
-#include <math.h>
-
-//
-// The classes
-//
-static VALUE rb_superstring;
-
-//
-// Utility macros.
-//
-#ifdef ONELINER_DEBUG
-#define DEBUG(s, ...) { \
- fprintf(stderr, "DEBUG: "); \
- fprintf(stderr, s, ## __VA_ARGS__); \
- fprintf(stderr, "\n"); \
- fflush(NULL); }
-#define IFDEBUG(s) s
-#define BITSTRING_DEBUG(msg,str,len) { \
- fprintf(stderr, "DEBUG: %s: ", (msg)); \
- rb_funcall(rb_const_get(rb_cObject, rb_intern("Kernel")), \
- rb_intern("print"), \
- 1, \
- rb_funcall(rb_funcall(rb_funcall(rb_str_new((gchar *) (str), (len)), \
- rb_intern("unpack"), \
- 1, \
- rb_str_new2("b*")), \
- rb_intern("first"), \
- 0), \
- rb_intern("gsub"), \
- 2, \
- rb_funcall(rb_const_get(rb_cObject, rb_intern("Regexp")), \
- rb_intern("new"), \
- 1, \
- rb_str_new2("(.{4,4})")), \
- rb_str_new2("\\1,"))); \
- fprintf(stderr, "\n"); \
- fflush(NULL); }
-#define STRING_DEBUG(msg,str,len) { \
- fprintf(stderr, "DEBUG: %s: ", (msg)); \
- rb_funcall(rb_const_get(rb_cObject, rb_intern("Kernel")), rb_intern("print"), 1, rb_funcall(rb_str_new((gchar *) (str), (len)), rb_intern("inspect"), 0)); \
- fprintf(stderr, "\n"); \
- fflush(NULL); }
-#else
-#define DEBUG(s, ...) ;
-#define IFDEBUG(s) ;
-#define BITSTRING_DEBUG(msg,str,len) ;
-#endif
-
-#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
-
-//
-// The c representation of a superstring.
-//
-typedef struct {
- // The blocks of this superstring.
- GArray *blocks;
- // The aux blocks of this superstring.
- GArray *aux_blocks;
- // Our graph of check blocks.
- GArray *graph;
- // Our graph of aux blocks for the source blocks.
- GArray *aux_graph_for_source_blocks;
- // Our graph of aux blocks for the aux blocks themselves.
- GArray *aux_graph_for_aux_blocks;
- // The size of each block in bits.
- guint32 block_size;
- // The number of guint8's needed to contain those bits.
- guint32 n_chars_in_block;
- // The length of the original data.
- guint32 data_len;
- // The number of blocks needed to contain that data.
- guint32 n_blocks_needed;
- // The number of bytes needed to store those blocks.
- guint32 n_bytes_for_blocks;
- // The number of aux blocks needed for those blocks.
- guint32 n_aux_blocks_needed;
- // The number of check blocks we have decoded so far.
- guint32 n_known_check_blocks;
- // Whether we have decided already that we are done decoding.
- gboolean decode_done;
-} oneliner_superstring;
-
-//
-// A random context.
-//
-typedef guint8 oneliner_context;
-
-static guint8 *
-oneliner_superstring_get_combined_block(oneliner_superstring *str, guint32 block_nr);
-static void
-oneliner_superstring_analyze(oneliner_superstring *str, guint32 found_block_nr);
-
-#include "context.c"
-#include "string.c"
-#include "xor_block.c"
-#include "graph_insertion.c"
-
-//
-// Return the block size in bits for a string of the given length.
-//
-static guint32
-oneliner_superstring_get_block_size(guint32 len) {
- if (len < 1024) {
- return (guint32) ceil((len / 1024.0) * 8.0);
- } else {
- return ((len / 128) / 8) * 8;
- }
-}
-
-//
-// Fill *block with a block_size (bitwise) piece of *data from pos (bitwise).
-//
-static void
-oneliner_superstring_get_block_from_data(guint8 *data, guint32 pos, guint32 block_size, guint8 *block)
-{
- //
- // Block sizes 1-7 are tricky,
- // but all other sizes are divisible by 8 and therefore ok to do with a simple memcpy.
- //
- if (block_size < 8) {
- // If the whole block fits within one char then we cant assume that we have permission
- // to read the char after it, but if it DOESNT then we MUST assume that we have permission
- // to read the char after it. Therefore the below fork where we read a char or a short from the data.
- if ((pos + block_size - 1) / 8 == pos / 8) {
- *block = data[pos / 8];
- *block = *block << (8 - ((pos + block_size) % 8)) % 8;
- *block = *block >> 8 - block_size;
- } else {
- guint16 short_containing_block = * (guint16 *) (data + (pos / 8));
- short_containing_block = short_containing_block << (8 - ((pos + block_size) % 8)) % 8;
- short_containing_block = short_containing_block >> 16 - block_size;
- *block = (guint8) short_containing_block;
- }
- } else {
- memcpy(block, data + (pos / 8), sizeof(guint8) * (block_size / 8));
- }
-}
-
-//
-// Take *data and return a GArray * with all the block_size blocks it contains.
-// Needs hints as to how many bytes we need to contain all blocks, how long *data is,
-// how many chars each block needs and how many blocks we need in total.
-//
-static GArray *
-oneliner_superstring_build_blocks_from_data(guint32 n_bytes_for_blocks,
- guint32 data_len,
- guint32 block_size,
- guint32 n_chars_in_block,
- guint32 n_blocks_needed,
- guint8 *data)
-{
- 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_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_nr) = tmp_block;
- }
-
- return rval;
-}
-
-
-//
-// Ensure that str->blocks contains a GArray with all the blocks of this data.
-//
-static void
-oneliner_superstring_build_blocks(oneliner_superstring *str, guint8 *data)
-{
- str->blocks = oneliner_superstring_build_blocks_from_data(str->n_bytes_for_blocks,
- str->data_len,
- str->block_size,
- str->n_chars_in_block,
- str->n_blocks_needed,
- data);
-}
-
-//
-// Take the block_size (bitwise) content of *block and insert it in *data at block_nr.
-//
-static void
-oneliner_superstring_set_data_from_block(guint8 *data, guint32 block_nr, guint32 block_size, guint8 *block)
-{
- //
- // If the block size is less than 8 then we have some tricky business, otherwise
- // we know that it is a multiple of 8, which makes it into a simple memcpy.
- //
- if (block_size < 8) {
- // If the entire block fits within one byte then we can not assume that we can write
- // the byte after, but if it doesnt then we MUST assume that we CAN write the byte
- // after, therefore the below fork where we write a char or a long depending.
- if ((block_nr * block_size) / 8 == (((block_nr + 1) * block_size) - 1) / 8) {
- // Set the byte we want to write to the block content.
- guint8 byte_to_write = *block;
- // Left shift it enough so that it matches the segment of data we want to write.
- byte_to_write = byte_to_write << (block_nr * block_size) % 8;
- // Then OR the corresponding byte in the data with the byte to write. Since
- // the data is supposed to be initialized with zeroes this ought to do the trick.
- data[(block_nr * block_size) / 8] = data[(block_nr * block_size) / 8] | byte_to_write;
- } else {
- // Set the short we want to write to the block content.
- guint16 short_to_write = (guint16) *block;
- // Left shift it enough so that it matches the segment of data we want to write.
- short_to_write = short_to_write << (block_nr * block_size) % 8;
- // Then OR the corresponding short in the data with the short to write. Since
- // the data is supposed to be initialized with zeroes this ought to do the trick.
- * (guint16 *) (data + (block_nr * block_size) / 8) = * (guint16 *) (data + (block_nr * block_size) / 8) | short_to_write;
- }
- } else {
- memcpy((gchar *) data + (block_nr * (block_size / 8)), (gchar *) block, sizeof(guint8) * (block_size / 8));
- }
-}
-
-//
-// Take the given blocks of size block_size needing n_bytes_for_blocks to be stored completely and
-// concatenate them into a string, then return the first data_len bytes of the result.
-//
-// If prepend_size is larger than 0 then the prepend string will be prepended to the result.
-//
-static guint8 *
-oneliner_superstring_build_data_from_blocks(guint32 n_bytes_for_blocks,
- guint32 data_len,
- guint32 block_size,
- GArray *blocks,
- guint32 prepend_size,
- guint8 *prepend)
-{
- guint32 index;
- guint8 *tmp_data = g_new0(guint8, n_bytes_for_blocks + prepend_size + 1);
- for (index = 0; index < blocks->len; index++) {
- oneliner_superstring_set_data_from_block(tmp_data + prepend_size, index, block_size, g_array_index(blocks, guint8 *, index));
- }
- memcpy((gchar *) tmp_data, (gchar *) prepend, sizeof(guint8) * prepend_size);
- return g_realloc(tmp_data, data_len);
-}
-
-//
-// Return the guint8 * that the given *str describes with its blocks.
-//
-static guint8 *
-oneliner_superstring_build_data(oneliner_superstring *str)
-{
- return oneliner_superstring_build_data_from_blocks(str->n_bytes_for_blocks,
- str->data_len,
- str->block_size,
- str->blocks,
- 0,
- NULL);
-}
-
-//
-// Create the aux_blocks GArray for *str using its blocks and length.
-//
-static void
-oneliner_superstring_build_aux_blocks(oneliner_superstring *str)
-{
- guint32 tmp;
- oneliner_context *context = oneliner_context_new();
-
- oneliner_context_seed(context, (gint32) str->data_len);
- str->aux_blocks = g_array_new(FALSE, TRUE, sizeof(guint8 *));
- g_array_set_size(str->aux_blocks, str->n_aux_blocks_needed);
-
- for (tmp = 0; tmp < str->n_blocks_needed; tmp++) {
- guint32 tmp2;
- for (tmp2 = 0; tmp2 < Q; tmp2++) {
- guint32 aux_block_nr = (guint32) RANDOM(context, str->n_aux_blocks_needed);
- if (g_array_index(str->aux_blocks, guint *, aux_block_nr) == NULL) {
- 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),
- str->n_chars_in_block);
- }
- }
- }
-
- g_free(context);
-}
-
-//
-// Initialize all the precalculated state of *str using data_len.
-//
-static void
-oneliner_superstring_initialize(oneliner_superstring *str, guint32 data_len)
-{
- // Make sure the length of our data (our String superclass content) is set.
- str->data_len = (guint32) data_len;
- // Make sure the block size we deem reasonable for this data length is set.
- str->block_size = oneliner_superstring_get_block_size(str->data_len);
- // Make sure the number of chars needed to contain such a block is set.
- str->n_chars_in_block = (guint32) ceil(str->block_size / 8.0);
- // Make sure the number of blocks needed to contain this data is set.
- str->n_blocks_needed = (guint32) ceil((str->data_len * 8.0) / str->block_size);
- // Make sure the number of bytes needed to contain those blocks is set.
- str->n_bytes_for_blocks = (guint32) ceil((str->n_blocks_needed * str->block_size) / 8.0);
- // Make sure the number of aux blocks needed for those blocks is set.
- str->n_aux_blocks_needed = (guint32) ceil(0.55 * Q * E * str->n_blocks_needed);
- // Make sure the number of known check blocks so far is set.
- str->n_known_check_blocks = 0;
- // Make sure we dont think we have decoded already.
- str->decode_done = FALSE;
-}
-
-//
-// Initialize a superstring using (possibly) a String to encode.
-//
-static VALUE
-rb_oneliner_superstring_initialize(int argc, VALUE *argv, VALUE self)
-{
- oneliner_superstring *str;
-
- if (argc > 1) {
- rb_raise(rb_eRuntimeError, "Oneliner::SuperString.new(String s = nil) takes at most 1 argument.");
- } else if (argc == 1) {
- Check_Type(argv[0], T_STRING);
-
- if (RSTRING(argv[0])->len < 1)
- rb_raise(rb_eRuntimeError, "First argument to Oneliner::SuperString.new(String s = nil) must be a String of at least size 1 if given.");
-
- RB_ONELINER(self, str);
-
- oneliner_superstring_initialize(str, RSTRING(argv[0])->len);
-
- // Make sure that we have our blocks calculated properly.
- oneliner_superstring_build_blocks(str, (guint8 *) RSTRING(argv[0])->ptr);
- oneliner_superstring_build_aux_blocks(str);
- }
- return self;
-}
-
-//
-// Returns whether *str is done decoding.
-//
-static VALUE
-oneliner_superstring_decode_done(oneliner_superstring *str)
-{
- guint32 tmp;
- if (str->decode_done)
- return Qtrue;
- if (str->blocks == NULL)
- return Qfalse;
- if (str->n_known_check_blocks < str->n_blocks_needed)
- return Qfalse;
- for (tmp = 0; tmp < str->n_blocks_needed; tmp++)
- if (g_array_index(str->blocks, guint8 *, tmp) == NULL)
- return Qfalse;
- str->decode_done = TRUE;
- return Qtrue;
-}
-
-//
-// Returns a GArray * containing all the blocks described by *chunk of length chunk_len
-// in the context of *str (its block_size, n_chars_in_block etc).
-//
-static GArray *
-oneliner_superstring_get_blocks_from_chunk(oneliner_superstring *str, guint8 *chunk, guint32 chunk_len)
-{
- return oneliner_superstring_build_blocks_from_data(chunk_len,
- chunk_len,
- str->block_size,
- str->n_chars_in_block,
- (chunk_len * 8) / str->block_size,
- chunk);
-}
-
-//
-// Return the guint8 * at either source or aux block with index block_nr in *str.
-//
-static guint8 *
-oneliner_superstring_get_combined_block(oneliner_superstring *str, guint32 block_nr)
-{
- if (block_nr < str->n_blocks_needed)
- return g_array_index(str->blocks, guint8 *, block_nr);
- else
- return g_array_index(str->aux_blocks, guint8 *, block_nr - str->n_blocks_needed);
-}
-
-//
-// Set either the source of aux block at block_nr of *str to *block.
-//
-static void
-oneliner_superstring_set_combined_block(oneliner_superstring *str, guint32 block_nr, guint8 *block)
-{
- if (block_nr < str->n_blocks_needed && g_array_index(str->blocks, guint8 *, block_nr) == NULL) {
- ALLOC_COPY8(g_array_index(str->blocks, guint8 *, block_nr), block, str->n_chars_in_block);
- } else if (g_array_index(str->aux_blocks, guint8 *, block_nr - str->n_blocks_needed) == NULL) {
- ALLOC_COPY8(g_array_index(str->aux_blocks, guint8 *, block_nr - str->n_blocks_needed), block, str->n_chars_in_block);
- }
-}
-
-static void
-oneliner_superstring_analyze_source_block_with_array(oneliner_superstring *str,
- GArray *ary,
- guint32 found_block_nr)
-{
- guint32 source_block_nr;
- GList *list_element;
- GList *list_head = g_array_index(ary, GList *, found_block_nr);
- oneliner_xor_block *xor_block;
-
- // For each xor_block-containing item in the list.
- for (list_element = list_head; list_element != NULL; list_element = g_list_next(list_element)) {
- // Fetch its xor_block
- xor_block = (oneliner_xor_block *) list_element->data;
-
- // Apply this new knowledge to it.
- oneliner_xor_block_apply(xor_block,
- str,
- found_block_nr);
-
- //
- // If that meant that it is finished then dance the dance of setting the combined block,
- // freeing the check block, removing it from the GList of check blocks for that combined block,
- // and analyzing the results.
- //
- // Otherwise if it is empty, just free it and remove it.
- //
- if (XOR_BLOCK_FINISHED(xor_block)) {
-
- // Find the source block that it defines.
- source_block_nr = oneliner_xor_block_last_source_block_nr(xor_block);
-
- // And set it.
- oneliner_superstring_set_combined_block(str,
- source_block_nr,
- xor_block->sum);
- // Then free the check block.
- oneliner_xor_block_free(xor_block);
-
- // Then remove it from our unresolved check blocks so that we can run analyze safely again.
- g_array_index(ary, GList *, found_block_nr) = g_list_remove_link(list_head, list_element);
-
- // Then remove the list element that contained this check block.
- g_list_free_1(list_element);
-
- // And now analyze what the newly found source block led to.
- // (Right, it can be an aux block as well, but my logic is still correct, I believe.)
- oneliner_superstring_analyze(str, source_block_nr);
- } else if (XOR_BLOCK_EMPTY(xor_block)) {
- // Free the check block.
- oneliner_xor_block_free(xor_block);
- // Remove it from our unresolved list.
- g_array_index(ary, GList *, found_block_nr) = g_list_remove_link(list_head, list_element);
- // And remove the list element.
- g_list_free_1(list_element);
- }
- }
-}
-
-static void
-oneliner_superstring_analyze_source_block(oneliner_superstring *str, guint32 found_block_nr)
-{
- oneliner_superstring_analyze_source_block_with_array(str,
- str->graph,
- found_block_nr);
-
- oneliner_superstring_analyze_source_block_with_array(str,
- str->aux_graph_for_source_blocks,
- found_block_nr);
-}
-
-static void
-oneliner_superstring_analyze_aux_block(oneliner_superstring *str, guint32 found_block_nr)
-{
- oneliner_xor_block *xor_block;
-
- if ((xor_block = g_array_index(str->aux_graph_for_aux_blocks,
- oneliner_xor_block *,
- found_block_nr - str->n_blocks_needed)) != NULL) {
- oneliner_xor_block_set_sum(xor_block, oneliner_superstring_get_combined_block(str, found_block_nr), str->n_chars_in_block);
- if (XOR_BLOCK_FINISHED(xor_block)) {
- guint32 source_block_nr = oneliner_xor_block_last_source_block_nr(xor_block);
-
- oneliner_superstring_set_combined_block(str,
- source_block_nr,
- xor_block->sum);
- oneliner_xor_block_free(xor_block);
-
- g_array_index(str->aux_graph_for_aux_blocks,
- oneliner_xor_block *,
- found_block_nr - str->n_blocks_needed) = NULL;
-
- oneliner_superstring_analyze(str, source_block_nr);
- } else if (XOR_BLOCK_EMPTY(xor_block)) {
- oneliner_xor_block_free(xor_block);
- g_array_index(str->aux_graph_for_aux_blocks,
- oneliner_xor_block *,
- found_block_nr - str->n_blocks_needed) = NULL;
- }
- }
-}
-
-static void
-oneliner_superstring_analyze(oneliner_superstring *str, guint32 found_block_nr)
-{
- if (found_block_nr < str->n_blocks_needed) {
- oneliner_superstring_analyze_source_block(str, found_block_nr);
- } else {
- oneliner_superstring_analyze_aux_block(str, found_block_nr);
- }
-}
-
-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;
- guint32 tmp2;
- guint32 unknown_source_blocks;
- guint32 unknown_source_block_nr;
- GList *inserts;
- oneliner_xor_block *xor_block;
- guint32 degree;
- guint32 block_nr;
- guint8 *block_content;
-
- oneliner_context_seed(context, (gint32) seed);
-
- content_blocks = oneliner_superstring_get_blocks_from_chunk(str, chunk, chunk_len);
-
- for (tmp = 0; tmp < content_blocks->len; tmp++) {
- degree = oneliner_context_get_degree(context);
- if (degree == 1) {
- block_nr = RANDOM(context, str->n_blocks_needed + str->n_aux_blocks_needed);
- oneliner_superstring_set_combined_block(str, block_nr, g_array_index(content_blocks, guint8 *, tmp));
- oneliner_superstring_analyze(str, block_nr);
- } else {
- unknown_source_blocks = 0;
- unknown_source_block_nr = 0;
- inserts = NULL;
-
- xor_block = oneliner_xor_block_new(g_array_index(content_blocks, guint8 *, tmp),
- str->n_chars_in_block,
- TRUE);
-
- for (tmp2 = 0; tmp2 < degree; tmp2++) {
- block_nr = RANDOM(context, str->n_blocks_needed + str->n_aux_blocks_needed);
- 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 (XOR_BLOCK_FINISHED(xor_block)) {
- oneliner_superstring_set_combined_block(str, unknown_source_block_nr, xor_block->sum);
-
- g_list_foreach(inserts, oneliner_graph_insertion_free_with_check_block, NULL);
- g_list_free(inserts);
-
- oneliner_superstring_analyze(str, unknown_source_block_nr);
- } else {
- g_list_foreach(inserts, oneliner_insertion_execute, str);
- g_list_free(inserts);
- }
-
- }
- (str->n_known_check_blocks)++;
- }
-
- g_array_free(content_blocks, TRUE);
- g_free(context);
-}
-
-static void
-oneliner_superstring_build_aux_graph(oneliner_superstring *str)
-{
- oneliner_context *context = oneliner_context_new();
- guint32 tmp;
- guint8 *zeroes = g_new0(guint8, str->n_chars_in_block);
- guint32 tmp2;
- guint32 aux_block_nr;
- oneliner_xor_block *aux_block;
- GList *aux_blocks;
-
- oneliner_context_seed(context, (gint32) str->data_len);
- str->aux_graph_for_aux_blocks = g_array_new(FALSE, TRUE, sizeof(oneliner_xor_block *));
- g_array_set_size(str->aux_graph_for_aux_blocks, str->n_aux_blocks_needed);
- str->aux_graph_for_source_blocks = g_array_new(FALSE, TRUE, sizeof(GList *));
- g_array_set_size(str->aux_graph_for_source_blocks, str->n_blocks_needed);
-
- for (tmp = 0; tmp < str->n_blocks_needed; tmp++) {
- aux_blocks = NULL;
-
- for (tmp2 = 0; tmp2 < Q; tmp2++) {
- aux_block_nr = RANDOM(context, str->n_aux_blocks_needed);
-
- if ((aux_block = g_array_index(str->aux_graph_for_aux_blocks, oneliner_xor_block *, aux_block_nr)) == NULL) {
- aux_block = oneliner_xor_block_new(zeroes, str->n_chars_in_block, FALSE);
- g_array_index(str->aux_graph_for_aux_blocks, oneliner_xor_block *, aux_block_nr);
- }
-
- oneliner_xor_block_add(aux_block, tmp);
- aux_blocks = g_list_append(aux_blocks, aux_block);
- }
-
- g_array_index(str->aux_graph_for_source_blocks, GList *, tmp) = aux_blocks;
- }
-
- g_free(zeroes);
- g_free(context);
-}
-
-static VALUE
-rb_oneliner_superstring_decode(VALUE self, VALUE chunk)
-{
- oneliner_superstring *str;
- guint32 data_len;
- guint32 seed;
- guint32 blocks_needed;
-
- Check_Type(chunk, T_STRING);
-
- RB_ONELINER(self, str);
-
- if (RSTRING(chunk)->len < 8)
- rb_raise(rb_eRuntimeError, "Oneliner::SuperString#decode(String chunk) needs an argument that is at least 8 characters long.");
-
- data_len = ((guint32 *) RSTRING(chunk)->ptr)[0];
- seed = ((guint32 *) RSTRING(chunk)->ptr)[1];
-
- if (str->data_len == 0) {
- str->data_len = data_len;
- } else if (str->data_len != data_len) {
- rb_raise(rb_eRuntimeError, "Oneliner::Superstring#decode(String chunk) needs all consecutive calls to be with arguments having the same first four characters. Didn't you use chunks produced using #encode calls from the same instance?");
- }
-
- if (str->blocks == NULL) {
- oneliner_superstring_initialize(str, data_len);
- str->blocks = g_array_new(FALSE, TRUE, sizeof(guint8 *));
- 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_array_new(FALSE, TRUE, sizeof(GList *));
- oneliner_superstring_build_aux_graph(str);
- }
-
- oneliner_superstring_add_to_graph(str, seed, (guint8 *) RSTRING(chunk)->ptr + 8, (guint32) RSTRING(chunk)->len - 8);
-
- return oneliner_superstring_decode_done(str);
-}
-
-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->n_blocks_needed + str->n_aux_blocks_needed);
- 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->n_blocks_needed + str->n_aux_blocks_needed)),
- str->n_chars_in_block);
-
- return rval;
-}
-
-static guint32
-oneliner_superstring_encode(oneliner_superstring *str, guint8 **buffer, guint32 len)
-{
- oneliner_context *context = oneliner_context_new();
- GArray *rval_ary = g_array_new(FALSE, FALSE, sizeof(guint8 *));
- guint8 prepend[8];
- gint32 tmp;
-
- sranddev();
- tmp = (gint32) rand();
- oneliner_context_seed(context, tmp);
-
- ( (guint32 *) prepend )[0] = str->data_len;
- ( (guint32 *) prepend )[1] = (guint32) tmp;
-
- while ((rval_ary->len * str->block_size) / 8 < len) {
- guint8 *check_block = oneliner_superstring_get_check_block(str, context);
- g_array_append_val(rval_ary, check_block);
- }
-
- // Here I let tmp describe the number of bytes needed to contain the rval_ary considering the block
- // size. And since we cant really truncate it at the end at this stage (like we can in the final build_data_from_blocks)
- // the data_len argument is the same as the n_bytes_for_blocks argument. Also, we want to prepend the original data-len
- // and seed, so we use the prepend argument.
- tmp = (guint32) ceil((rval_ary->len * str->block_size) / 8);
- *buffer = oneliner_superstring_build_data_from_blocks(tmp,
- tmp,
- str->block_size,
- rval_ary,
- 8,
- prepend);
- g_free(context);
- g_array_free(rval_ary, TRUE);
-
- return tmp;
-}
-
-static void
-oneliner_superstring_free_xor_block(gpointer xor_block, gpointer user_data)
-{
- oneliner_xor_block_free((oneliner_xor_block *) xor_block);
-}
-
-static void
-oneliner_superstring_free_ary_of_glists_of_xor_blocks(GArray *ary, gboolean free_xor_blocks)
-{
- guint32 tmp;
- for (tmp = 0; tmp < ary->len; tmp++) {
- GList *list;
- if ((list = (GList *) g_array_index(ary, GList *, tmp)) != NULL) {
- if (free_xor_blocks)
- g_list_foreach(list, oneliner_superstring_free_xor_block, NULL);
- g_list_free(list);
- }
- }
- g_array_free(ary, FALSE);
-}
-
-static void
-oneliner_superstring_free(oneliner_superstring *str)
-{
- guint32 tmp;
- 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)
- oneliner_superstring_free_ary_of_glists_of_xor_blocks(str->graph, TRUE);
- if (str->aux_graph_for_aux_blocks != NULL) {
- for (tmp = 0; tmp < str->n_aux_blocks_needed; tmp++)
- oneliner_xor_block_free((oneliner_xor_block *) g_array_index(str->aux_graph_for_aux_blocks, oneliner_xor_block *, tmp));
- }
- if (str->aux_graph_for_source_blocks != NULL)
- oneliner_superstring_free_ary_of_glists_of_xor_blocks(str->aux_graph_for_source_blocks, FALSE);
-
- g_free(str);
-}
-
-static VALUE
-rb_oneliner_superstring_alloc(VALUE klass)
-{
- oneliner_superstring *str = g_new0(oneliner_superstring, 1);
- return Data_Wrap_Struct(klass, NULL, oneliner_superstring_free, str);
-}
-
-static VALUE
-oneliner_superstring_get_blocks(GArray *container, guint32 len)
-{
- guint32 tmp;
- VALUE rval = rb_ary_new();
- for (tmp = 0; tmp < container->len; tmp++) {
- guint8 *tmp_block = g_array_index(container, guint8 *, tmp);
- rb_ary_push(rval, rb_str_new((gchar *) tmp_block, len));
- }
- return rval;
-}
-
-static VALUE
-rb_oneliner_superstring_blocks(VALUE self)
-{
- oneliner_superstring *str;
- RB_ONELINER(self, str);
- return oneliner_superstring_get_blocks(str->blocks, str->n_chars_in_block);
-}
-
-static VALUE
-rb_oneliner_superstring_aux_blocks(VALUE self)
-{
- oneliner_superstring *str;
- RB_ONELINER(self, str);
- return oneliner_superstring_get_blocks(str->aux_blocks, str->n_chars_in_block);
-}
-
-static VALUE
-rb_oneliner_superstring_to_s(VALUE self)
-{
- oneliner_superstring *str;
- VALUE rval;
- guint8 *tmp_data;
-
- RB_ONELINER(self, str);
- if (str->blocks == NULL)
- return rb_str_new2("");
- tmp_data = oneliner_superstring_build_data(str);
- rval = rb_str_new((gchar *) tmp_data, str->data_len);
- g_free(tmp_data);
- return rval;
-}
-
-static VALUE
-rb_oneliner_superstring_block_size(VALUE self)
-{
- oneliner_superstring *str;
- RB_ONELINER(self, str);
- return INT2NUM(str->block_size);
-}
-
-static VALUE
-rb_oneliner_superstring_encode(VALUE self, VALUE size)
-{
- guint8 *chunk;
- VALUE rval;
- oneliner_superstring *str;
- guint32 chunk_size;
-
- Check_Type(size, T_FIXNUM);
- if (NUM2INT(size) < 8)
- rb_raise(rb_eRuntimeError, "Oneliner::SuperString#encode(Fixnum size) needs a size of at least 8.");
-
- RB_ONELINER(self, str);
-
- chunk_size = oneliner_superstring_encode(str, &chunk, NUM2INT(size));
- rval = rb_str_new((gchar *) chunk, chunk_size);
-
- g_free(chunk);
-
- return rval;
-}
-
-static VALUE
-rb_oneliner_superstring_chunk_blocks(VALUE self, VALUE chunk)
-{
- oneliner_superstring *str;
- VALUE rval;
- GArray *blocks;
-
- Check_Type(chunk, T_STRING);
-
- if (RSTRING(chunk)->len < 8)
- rb_raise(rb_eRuntimeError, "Oneliner::SuperString.chunk_blocks(String chunk) needs an argument that is at least 8 characters long.");
-
- RB_ONELINER(self, str);
- blocks = oneliner_superstring_get_blocks_from_chunk(str,
- (guint8 *) RSTRING(chunk)->ptr + 8,
- (guint32) RSTRING(chunk)->len - 8);
- rval = oneliner_superstring_get_blocks(blocks,
- str->n_chars_in_block);
- g_array_free(blocks, TRUE);
- return rval;
-}
-
-#ifdef __cplusplus
-extern "C" {
-#endif
- void Init_oneliner_ext() {
- VALUE rb_string = rb_define_class("String", rb_cObject);
- rb_define_method(rb_string, "xor!", rb_oneliner_string_xor, 1);
-
- rb_superstring = rb_define_class_under(rb_define_module("Oneliner"),
- "SuperString",
- rb_cObject);
- rb_define_alloc_func(rb_superstring, rb_oneliner_superstring_alloc);
- rb_define_method(rb_superstring, "initialize", rb_oneliner_superstring_initialize, -1);
- rb_define_method(rb_superstring, "blocks", rb_oneliner_superstring_blocks, 0);
- rb_define_method(rb_superstring, "aux_blocks", rb_oneliner_superstring_aux_blocks, 0);
- rb_define_method(rb_superstring, "to_s", rb_oneliner_superstring_to_s, 0);
- rb_define_method(rb_superstring, "encode", rb_oneliner_superstring_encode, 1);
- rb_define_method(rb_superstring, "block_size", rb_oneliner_superstring_block_size, 0);
- rb_define_method(rb_superstring, "chunk_blocks", rb_oneliner_superstring_chunk_blocks, 1);
- rb_define_method(rb_superstring, "decode", rb_oneliner_superstring_decode, 1);
- }
-#ifdef __cplusplus
-}
-#endif
-
More information about the Archipelago-submits
mailing list