[Archipelago-submits] [275] trunk/oneliner: a bit further along the road
nobody at rubyforge.org
nobody at rubyforge.org
Sat May 19 15:32:26 EDT 2007
Revision: 275
Author: zond
Date: 2007-05-19 15:32:26 -0400 (Sat, 19 May 2007)
Log Message:
-----------
a bit further along the road
Modified Paths:
--------------
trunk/oneliner/ext/oneliner_ext.c
trunk/oneliner/tests/superstring_test.rb
Added Paths:
-----------
trunk/oneliner/tests/string_test.rb
Modified: trunk/oneliner/ext/oneliner_ext.c
===================================================================
--- trunk/oneliner/ext/oneliner_ext.c 2007-05-18 12:49:21 UTC (rev 274)
+++ trunk/oneliner/ext/oneliner_ext.c 2007-05-19 19:32:26 UTC (rev 275)
@@ -31,19 +31,39 @@
// 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_str_new((gchar *) (str), (len)), rb_intern("unpack"), 1, rb_str_new2("B*"))); fprintf(stderr, "\n"); fflush(NULL)
+#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 GUINT32MAX 0xffffffff
#define RANDOM(context,max) (oneliner_context_random(context) % (max))
-#define RANDFLOAT(context) ( (gdouble) oneliner_context_random(context) ) / ( (gdouble) GUINT32MAX )
+#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 COMBINE_BLOCK(str,block_no) (block_no < str->blocks->len ? g_array_index((str)->blocks, guint8 *, block_no) : g_array_index((str)->aux_blocks, guint8 *, block_no - str->blocks->len))
#define Q 3
#define E 0.01
@@ -145,6 +165,23 @@
}
//
+// Get a random degree
+//
+static guint32
+oneliner_context_get_degree(oneliner_context *context)
+{
+ gdouble f;
+ guint32 tmp = 0;
+
+ f = RANDFLOAT(context);
+ while (f > 0) {
+ tmp++;
+ f = f - P[tmp];
+ }
+ return tmp;
+}
+
+//
// Make object into object ^ subject
//
static void
@@ -153,37 +190,27 @@
guint32 tmp;
#ifdef G_HAVE_GINT64
- for (tmp = 0; tmp < len / 8; tmp++) {
+ for (tmp = 0; tmp < len / 8; tmp++)
( (guint64 *) object )[tmp] = ( (guint64 *) object )[tmp] ^ ( (guint64 *) subject )[tmp];
- }
- for (tmp = 0; tmp < (len % 8) / 4; tmp++) {
- object[len - tmp - 1] = object[len - tmp - 1] ^ subject[len - tmp - 1];
- }
+ for (tmp = tmp * 2; tmp < len / 4; tmp++)
+ ( (guint32 *) object )[tmp] = ( (guint32 *) object )[tmp] ^ ( (guint32 *) subject )[tmp];
+ for (tmp = tmp * 4; tmp < len; tmp++)
+ object[tmp] = object[tmp] ^ subject[tmp];
#else
- for (tmp = 0; tmp < len / 4; tmp++) {
+ for (tmp = 0; tmp < len / 4; tmp++)
( (guint32 *) object )[tmp] = ( (guint32 *) object )[tmp] ^ ( (guint32 *) subject )[tmp];
- }
- for (tmp = 0; tmp < (len % 4); tmp++) {
- object[len - tmp - 1] = object[len - tmp - 1] ^ subject[len - tmp - 1];
- }
+ for (tmp = tmp * 4; tmp < len; tmp++)
+ object[tmp] = object[tmp] ^ subject[tmp];
#endif
}
-//
-// Get a random degree
-//
-static guint32
-oneliner_context_get_degree(guint8 *context)
+static VALUE
+rb_oneliner_string_xor(VALUE self, VALUE object)
{
- gdouble f;
- guint32 tmp = 0;
-
- f = RANDFLOAT(context);
- while (f > 0) {
- tmp++;
- f = f - P[tmp];
- }
- return tmp;
+ Check_Type(object, T_STRING);
+ rb_str_modify(self);
+ oneliner_string_xor((guint8 *) RSTRING(self)->ptr, (guint8 *) RSTRING(object)->ptr, MIN(RSTRING(self)->len, RSTRING(object)->len));
+ return self;
}
//
@@ -191,11 +218,10 @@
//
static guint32
oneliner_get_block_size(guint32 len) {
- return 2;
if (len < 1024) {
return (guint32) ceil((len / 1024.0) * 8.0);
} else {
- return (len * 8) / 1024;
+ return ((len / 128) / 8) * 8;
}
}
@@ -204,31 +230,24 @@
{
//
// Block sizes 1-7 are tricky,
- // but all other sizes are divisible by 8 and therefore ok to do with a simple strncpy.
+ // 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) {
- // Set the block content to whatever is at the char that contains the entire block.
*block = data[pos / 8];
- // Left shift it to get rid of any bits before it in the char.
- *block = *block << pos % 8;
- // Then right shift if all the way to the right to get the right number.
+ *block = *block << (8 - ((pos + block_size) % 8)) % 8;
*block = *block >> 8 - block_size;
} else {
- // Set a temporary short to whatever is at the first and second chat that contains the entire block.
guint16 short_containing_block = * (guint16 *) (data + (pos / 8));
- // Left shift it to get rid of any bits before it in the short.
- short_containing_block = short_containing_block << pos % 8;
- // Then right shift it all the way to the right to get the right number.
+ short_containing_block = short_containing_block << (8 - ((pos + block_size) % 8)) % 8;
short_containing_block = short_containing_block >> 16 - block_size;
- // Then set the block content to whatever is at the lower part of the short.
*block = (guint8) short_containing_block;
}
} else {
- strncpy((gchar *) block, (gchar *) data + (pos / 8), block_size / 8);
+ memcpy(block, data + (pos / 8), sizeof(guint8) * (block_size / 8));
}
}
@@ -240,17 +259,15 @@
{
guint32 pos;
guint8 *tmp_block;
- guint8 *tmp_data = g_new0(guint8, str->n_bytes_for_blocks);
+ guint8 tmp_data[str->n_bytes_for_blocks];
- strncpy((gchar *) tmp_data, (gchar *) data, str->n_bytes_for_blocks);
+ memcpy((gchar *) tmp_data, (gchar *) data, sizeof(guint8) * str->data_len);
str->blocks = g_array_new(FALSE, FALSE, sizeof(guint8 *));
for (pos = 0; pos < str->n_bytes_for_blocks * 8; pos += str->block_size) {
tmp_block = g_new0(guint8, str->n_chars_in_block + 1);
oneliner_superstring_get_block_from_data(tmp_data, pos, str->block_size, tmp_block);
g_array_append_val(str->blocks, tmp_block);
}
-
- g_free(tmp_data);
}
static void
@@ -258,7 +275,7 @@
{
//
// 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 strncpy.
+ // 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
@@ -268,7 +285,7 @@
// 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 << 8 - block_size - ((block_nr * block_size) % 8);
+ 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;
@@ -276,27 +293,36 @@
// 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 << 8 - (((block_nr + 1) * block_size) % 8);
+ 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 {
- strncpy((gchar *) data + (block_nr * (block_size / 8)), (gchar *) block, block_size / 8);
+ 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)
+ GArray *blocks,
+ guint32 prepend_size,
+ guint8 *prepend)
{
guint32 index;
- guint8 *tmp_data = g_new0(guint8, n_bytes_for_blocks);
+ 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, index, block_size, g_array_index(blocks, guint8 *, 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);
}
@@ -306,7 +332,9 @@
return oneliner_superstring_build_data_from_blocks(str->n_bytes_for_blocks,
str->data_len,
str->block_size,
- str->bloks);
+ str->blocks,
+ 0,
+ NULL);
}
static void
@@ -315,17 +343,19 @@
guint32 tmp;
oneliner_context *context = oneliner_context_new();
guint32 n_aux_blocks_needed = (guint32) ceil(0.55 * Q * E * str->blocks->len);
+
oneliner_context_seed(context, (gint32) str->data_len);
- str->aux_blocks = g_array_new(FALSE, FALSE, sizeof(guint8 *));
+ str->aux_blocks = g_array_new(FALSE, TRUE, sizeof(guint8 *));
g_array_set_size(str->aux_blocks, n_aux_blocks_needed);
+
for (tmp = 0; tmp < str->blocks->len; tmp++) {
guint32 aux_block_nr = (guint32) RANDOM(context, n_aux_blocks_needed);
- guint8 *data_block = g_array_index(str->blocks, guint8 *, tmp);
if (g_array_index(str->aux_blocks, guint *, aux_block_nr) == NULL) {
- g_array_insert_val(str->aux_blocks, aux_block_nr, data_block);
+ g_array_index(str->aux_blocks, guint8 *, aux_block_nr) = (guint8 *) strdup(g_array_index(str->blocks, gchar *, tmp));
} else {
- guint8 *current_aux_block = g_array_index(str->aux_blocks, guint8 *, aux_block_nr);
- oneliner_string_xor(current_aux_block, data_block, str->n_chars_in_block);
+ 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);
}
}
@@ -336,7 +366,7 @@
// Encode a SuperString
//
static VALUE
-oneliner_superstring_initialize(int argc, VALUE *argv, VALUE self)
+rb_oneliner_superstring_initialize(int argc, VALUE *argv, VALUE self)
{
oneliner_superstring *str;
@@ -378,21 +408,54 @@
}
static guint8 *
-oneliner_superstring_encode(oneliner_superstring *str, guint32 len)
+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 *) COMBINE_BLOCK(str, block_nr));
+ guint32 tmp;
+
+ for (tmp = 2; tmp <= degree; tmp++)
+ oneliner_string_xor(rval, COMBINE_BLOCK(str, RANDOM(context, str->blocks->len + str->aux_blocks->len)), 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();
- guint8 *rval = g_new(guint8, len);
+ 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 *) rval )[0] = str->data_len;
- ( (guint32 *) rval )[1] = (guint32) seed;
- while (
+ ( (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
@@ -400,11 +463,12 @@
{
guint32 tmp;
g_array_free(str->blocks, TRUE);
+ g_array_free(str->aux_blocks, TRUE);
g_free(str);
}
static VALUE
-oneliner_superstring_alloc(VALUE klass)
+rb_oneliner_superstring_alloc(VALUE klass)
{
oneliner_superstring *str = g_new0(oneliner_superstring, 1);
return Data_Wrap_Struct(klass, NULL, oneliner_superstring_free, str);
@@ -423,7 +487,7 @@
}
static VALUE
-oneliner_superstring_blocks(VALUE self)
+rb_oneliner_superstring_blocks(VALUE self)
{
oneliner_superstring *str;
RB_ONELINER(self, str);
@@ -431,7 +495,7 @@
}
static VALUE
-oneliner_superstring_aux_blocks(VALUE self)
+rb_oneliner_superstring_aux_blocks(VALUE self)
{
oneliner_superstring *str;
RB_ONELINER(self, str);
@@ -439,7 +503,7 @@
}
static VALUE
-oneliner_superstring_to_s(VALUE self)
+rb_oneliner_superstring_to_s(VALUE self)
{
oneliner_superstring *str;
VALUE rval;
@@ -451,19 +515,53 @@
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) < 9)
+ rb_raise(rb_eRuntimeError, "Oneliner::SuperString#encode(Fixnum size) needs a size larger than 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;
+}
+
#ifdef __cplusplus
extern "C" {
#endif
void Init_oneliner_ext() {
- VALUE string = rb_const_get(rb_cObject, rb_intern("String"));
+ 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, oneliner_superstring_alloc);
- rb_define_method(rb_superstring, "initialize", oneliner_superstring_initialize, -1);
- rb_define_method(rb_superstring, "blocks", oneliner_superstring_blocks, 0);
- rb_define_method(rb_superstring, "aux_blocks", oneliner_superstring_aux_blocks, 0);
- rb_define_method(rb_superstring, "to_s", oneliner_superstring_to_s, 0);
+ 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);
}
#ifdef __cplusplus
}
Added: trunk/oneliner/tests/string_test.rb
===================================================================
--- trunk/oneliner/tests/string_test.rb (rev 0)
+++ trunk/oneliner/tests/string_test.rb 2007-05-19 19:32:26 UTC (rev 275)
@@ -0,0 +1,19 @@
+
+require File.join(File.dirname(__FILE__), 'test_helper')
+
+class StringTest < Test::Unit::TestCase
+
+ def test_xor
+ 100.times do |n|
+ print("(#{n})")
+ s = "x" * n
+ s2 = s.clone
+ s2.xor!("x" * n)
+ s3 = s2.clone
+ s3.xor!("x" * n)
+ assert_equal("\000" * n, s2)
+ assert_equal(s, s3)
+ end
+ end
+
+end
Modified: trunk/oneliner/tests/superstring_test.rb
===================================================================
--- trunk/oneliner/tests/superstring_test.rb 2007-05-18 12:49:21 UTC (rev 274)
+++ trunk/oneliner/tests/superstring_test.rb 2007-05-19 19:32:26 UTC (rev 275)
@@ -6,16 +6,16 @@
def test_blocks
8.times do |m|
n = 128 * m + 63
- print("(#{n})")
s1 = "x" * n
s2 = Oneliner::SuperString.new(s1)
+ print("(#{s1.size}:#{s2.block_size})")
assert_equal(s1, s2.to_s)
end
- 1.upto(4) do |m|
+ 2.upto(10) do |m|
n = 1024 * m + 511
- print("(#{n})")
s1 = "x" * n
s2 = Oneliner::SuperString.new(s1)
+ print("(#{s1.size}:#{s2.block_size})")
assert_equal(s1, s2.to_s)
end
end
More information about the Archipelago-submits
mailing list