[Archipelago-submits] [262] trunk/oneliner: new approach, possibly much worse? more clever acting superstring with graph logic and stuff - not faster, but not really optimized either (at least not with c extension).
nobody at rubyforge.org
nobody at rubyforge.org
Sun Apr 15 16:24:01 EDT 2007
Revision: 262
Author: zond
Date: 2007-04-15 16:23:58 -0400 (Sun, 15 Apr 2007)
Log Message:
-----------
new approach, possibly much worse? more clever acting superstring with graph logic and stuff - not faster, but not really optimized either (at least not with c extension). one bug still there, that happens only sometimes.
Modified Paths:
--------------
trunk/oneliner/ext/oneliner_ext.c
trunk/oneliner/lib/oneliner/superstring.rb
Modified: trunk/oneliner/ext/oneliner_ext.c
===================================================================
--- trunk/oneliner/ext/oneliner_ext.c 2007-04-15 09:04:36 UTC (rev 261)
+++ trunk/oneliner/ext/oneliner_ext.c 2007-04-15 20:23:58 UTC (rev 262)
@@ -216,48 +216,6 @@
return INT2NUM(tmp);
}
-//
-// Use context to check if the degree blocks adjacent to block
-// can lead to anything good.
-//
-static VALUE
-superstring_decode_multiple(VALUE self, VALUE block_data, VALUE blocks, VALUE nr_of_blocks)
-{
- VALUE get_func = rb_intern("[]");
- VALUE set_func = rb_intern("[]=");
- VALUE this_block;
- VALUE block = rb_funcall(block_data, get_func, 1, INT2NUM(0));
- VALUE block_numbers = rb_funcall(block_data, get_func, 1, INT2NUM(1));
- int degree = RARRAY(block_numbers)->len;
- int tmp;
- int got_new_block = 0;
- int missing_blocks = degree;
- int _nr_of_blocks = NUM2INT(nr_of_blocks);
- int missing_block_nr;
-
- for (tmp = 0; tmp < degree; tmp++) {
- int block_nr = NUM2INT(rb_funcall(block_numbers, get_func, 1, INT2NUM(tmp)));
- if ((this_block = rb_funcall(blocks, get_func, 1, INT2NUM(block_nr))) != Qnil) {
- rb_str_modify(block);
- _string_xor2(RSTRING(block)->ptr, RSTRING(this_block)->ptr, RSTRING(this_block)->len);
- rb_funcall(block_numbers, set_func, 2, INT2NUM(tmp), Qnil);
- missing_blocks--;
- } else {
- missing_block_nr = block_nr;
- }
- }
-
- rb_funcall(block_numbers, rb_intern("compact!"), 0);
-
- if (missing_blocks == 1) {
- rb_funcall(blocks, set_func, 2, INT2NUM(missing_block_nr), block);
- got_new_block = 1;
- }
-
- return got_new_block ? Qtrue : Qfalse;
-}
-
-
VALUE rb_superstring;
VALUE rb_context;
@@ -281,7 +239,6 @@
rb_define_method(string, "^=", string_xor2, 1);
rb_define_method(string, "hack", string_hack, 1);
rb_define_method(rb_superstring, "get_degree", superstring_get_degree, 1);
- rb_define_method(rb_superstring, "decode_multiple", superstring_decode_multiple, 3);
}
#ifdef __cplusplus
}
Modified: trunk/oneliner/lib/oneliner/superstring.rb
===================================================================
--- trunk/oneliner/lib/oneliner/superstring.rb 2007-04-15 09:04:36 UTC (rev 261)
+++ trunk/oneliner/lib/oneliner/superstring.rb 2007-04-15 20:23:58 UTC (rev 262)
@@ -19,7 +19,7 @@
require 'digest/sha2'
module Oneliner
-
+
#
# A String subclass providing Online Code functionality.
#
@@ -28,12 +28,81 @@
E = 0.01
Q = 3
F = (Math.log((E ** 2) / 4) / Math.log(1 - (E / 2))).abs.to_i
- P = [0, (1 - ((1 + (1 / F)) / (1 + E)))]
- 2.upto(F) do |i|
- P << (((1 - P[1]) * F) / ((F - 1) * i * (i - 1)))
+
+ #
+ # A class that represents a block created from xoring other blocks.
+ #
+ class XORBlock
+ attr_accessor :xor_sum, :source_blocks
+ #
+ # Initialize the XORBlock with the given +xor_sum+ and an empty hash of source blocks.
+ #
+ def initialize(xor_sum)
+ @xor_sum = xor_sum
+ @source_blocks = {}
+ end
+ #
+ # Record that the given +source_block_nr+ is a part of this check block (one more time,
+ # if necessary).
+ #
+ def <<(source_block_nr)
+ @source_blocks[source_block_nr] ||= 0
+ @source_blocks[source_block_nr] += 1
+ end
+ #
+ # Return whether we are
+ # :finished (our xor_sum represents the value of the sole remaining source block)
+ # :empty (we can just as well be deleted, we can not be of any good)
+ # or :running (we need more data to reach a conclusion)
+ #
+ def state
+ case @source_blocks.size
+ when 1
+ if @source_blocks.values.first % 2 == 1
+ :finished
+ else
+ :empty
+ end
+ when 0
+ :empty
+ else
+ :running
+ end
+ end
+ #
+ # Record that the +found_block_nr+ has +value+ and delete it from our set of source blocks.
+ #
+ def apply(found_block_nr, value)
+ #puts "#{self.inspect}.apply(#{found_block_nr}, #{value.inspect})"
+ while @source_blocks[found_block_nr] > 0
+ @xor_sum ^= value
+ @source_blocks[found_block_nr] -= 1
+ end
+ @source_blocks.delete(found_block_nr)
+ #puts "and now we have #{@source_blocks.size} blocks left, and our state is #{state}"
+ end
end
#
+ # AuxBlocks are just like XORBlocks but they need to be
+ # accounted for even if we dont know their xor_sum yet...
+ #
+ class AuxBlock < XORBlock
+ attr_accessor :block_nr
+ def initialize(block_nr)
+ @xor_sum = nil
+ @source_blocks = {}
+ @block_nr = block_nr
+ end
+ def apply(found_block_nr, value)
+ if @xor_sum.nil?
+ @xor_sum = "\000" * value.size
+ end
+ super
+ end
+ end
+
+ #
# Will return a String containing +requested_size+ nr of bytes
# as an online coded chunk of blocks for this SuperString.
#
@@ -67,8 +136,6 @@
def decode!(chunk)
raise "#{chunk.inspect} is too small for metadata (8 bytes)" unless chunk.size > 7
- @decode_done = nil
-
context = Context.new
requested_size = chunk[0..3].unpack("i").first
@@ -77,15 +144,10 @@
the_seed = chunk[4..7].unpack("i").first
- chunk_data = build_chunk_data(chunk, context, the_seed)
-
- @known_nr_of_blocks += chunk_data.size
- @known_chunks.unshift(chunk_data)
+ add_to_graph(chunk, context, the_seed)
if @known_nr_of_blocks > @nr_of_blocks
-
- nil while do_decode(context)
-
+
if decode_done?
self.replace(compact(@blocks[0... at nr_of_data_blocks])[0...requested_size])
return true
@@ -118,29 +180,6 @@
#
#
- # Builds a Hash with index of each block in the +chunk+
- # paired with the block itself and the source blocks for
- # that block determined using +context+ and +the_seed+.
- #
- def build_chunk_data(chunk, context, the_seed)
- blocks_to_return = {}
-
- context.seed(the_seed)
-
- expand(chunk[8..-1]).each_with_index do |block, index|
- this_degree = get_degree(context)
- these_blocks = []
- this_degree.times do |m|
- these_blocks << context.random(@nr_of_blocks)
- end
-
- blocks_to_return[index] = [block, these_blocks]
- end
-
- return blocks_to_return
- end
-
- #
# Split +s+ up into @block_size (in bits if less than 8, otherwise closed matching nr of bytes) pieces
# and return them in an array.
#
@@ -207,99 +246,337 @@
# Decoding stuff
#
- def do_decode(context)
- found_new_block = false
- @known_chunks.clone.each_with_index do |chunk_data, i|
- this_chunk_found_new_block, this_chunk_informative = decode_chunk(chunk_data)
- found_new_block = found_new_block || this_chunk_found_new_block
- @known_chunks.delete(i) unless this_chunk_informative
+ #
+ # Initial decoding and graph building. ARGH!!!1111eleven
+ #
+ def add_to_graph(chunk, context, the_seed)
+
+ #
+ # Initialize the context so that we get the same rand numbers as when we built the chunk.
+ #
+ context.seed(the_seed)
+
+ #
+ # Everything except the first 8 chars of the chunk are check blocks.
+ #
+ chunk_blocks = expand(chunk[8..-1])
+ @known_nr_of_blocks += chunk_blocks.size
+
+ #
+ # Go through the chunk...
+ #
+ class << chunk_blocks
+ alias :add_to_graph_each :each
end
- return aux_decode || found_new_block
- end
+ chunk_blocks.add_to_graph_each do |block|
- def aux_decode
- got_new_block = false
+ #
+ # Get the degree from the context.
+ #
+ degree_for_this_block = get_degree(context)
- @nr_of_data_blocks.upto(@nr_of_blocks - 1) do |i|
+ #
+ # If we have the nice case of a single-source-block check block
+ # we just set the block and remember to see if it leads somewhere.
+ #
+ # Else we have a merry go round of fucking forks...
+ #
+ if degree_for_this_block == 1
+ found_block_nr = context.random(@nr_of_blocks)
+ @blocks[found_block_nr] = block
+ #puts "single source: \##{found_block_nr} = #{block.inspect}"
+ analyze(found_block_nr, block)
+ else
+ #
+ # Build a graph component with the block.
+ #
+ check_block = XORBlock.new(block)
- aux_block = @blocks[i]
- if aux_block
+ #
+ # Remember where this check block is supposed to be inserted.
+ #
+ inserts = []
+
+ #
+ # For each wanted source block...
+ #
+ degree_for_this_block.times do |m|
+ #
+ # Find it from the context.
+ #
+ this_source_block_nr = context.random(@nr_of_blocks)
- source_blocks = @aux_hash[i]
- if source_blocks.size == 1
- block_nr = source_blocks.first
+ #
+ # If we already have this block, just modify the xor_sum accordingly, otherwise...
+ #
+ if (known_block = @blocks[this_source_block_nr])
+ check_block.xor_sum ^= known_block
+ #puts "#{degree_for_this_block} known source: \##{this_source_block_nr} = #{known_block.inspect}"
+ else
+ #
+ # Add this source source block nr to our known source blocks.
+ #
+ check_block << this_source_block_nr
- if @blocks[block_nr].nil?
- @blocks[block_nr] = aux_block
- got_new_block = true
- @blocks[i] = nil
+ #
+ # Get (and possibly set) the check block array for this source block
+ # and add our data to it.
+ #
+ inserts << {
+ :set => check_blocks_for_this_source_block = (@graph[this_source_block_nr] ||= Set.new),
+ :value => check_block
+ }
+ #puts "#{degree_for_this_block} unknown source: \##{this_source_block_nr}"
end
- else
- missing_blocks = source_blocks.size
- missing_block = nil
- xor_sum = aux_block
- source_blocks.each do |block|
- source_block = @blocks[block]
- if source_block
- missing_blocks -= 1
- xor_sum ^= source_block
- else
- missing_block = block
- end
+ end
+
+ #
+ # If we only had one missing block, then we can remember it and see if it leads someplace.
+ #
+ # Otherwise insert it wherever it was supposed to be inserted.
+ #
+ case check_block.state
+ when :finished
+ @blocks[new_block = check_block.source_blocks.keys.first] = check_block.xor_sum
+ #puts "#{degree_for_this_block} source: \##{new_block} = #{check_block.xor_sum.inspect}"
+ analyze(new_block, check_block.xor_sum)
+ when :running
+ inserts.each do |insert|
+ s = insert[:set]
+ s << insert[:value]
end
+ end
+ end
+ end
- if missing_blocks == 1
- @blocks[missing_block] = xor_sum
- got_new_block = true
- @blocks[i] = nil
- end
+ end
+
+ #
+ # Analyze what we can conclude from a known block.
+ #
+ def analyze_block(block_nr, block_value)
+ #
+ # Remember what we want to analyze when this is done.
+ #
+ to_analyze = []
+
+ #
+ # If we have any unresolved check blocks for this block.
+ #
+ if unresolved_check_blocks_for_this_block = @graph[block_nr]
+ #
+ # For each such block...
+ #
+ unresolved_check_blocks_for_this_block.clone.each do |check_block|
+ #
+ # Apply our newly found knowledge.
+ #
+ check_block.apply(block_nr, block_value)
+
+ #
+ # Remove this check block from the list of check blocks for this block.
+ #
+ unresolved_check_blocks_for_this_block.delete(check_block)
+
+ #
+ # If the check block has finished its career and contains useful data.
+ #
+ if check_block.state == :finished
+ #
+ # Record the found block.
+ #
+ @blocks[new_block = check_block.source_blocks.keys.first] = check_block.xor_sum
+
+ #
+ # Remove this check block from the found block, and if empty remove the
+ # check block list for it.
+ #
+ unresolved_check_blocks_for_found_block = @graph[new_block]
+ unresolved_check_blocks_for_found_block.delete(check_block)
+ @graph.delete(new_block) if unresolved_check_blocks_for_found_block.empty?
+
+ #puts "\##{block_nr} = #{block_value.inspect} => \##{new_block} = #{check_block.xor_sum.inspect}"
+
+ #
+ # Remember to analyze the results of this.
+ #
+ to_analyze << [new_block, check_block.xor_sum]
+ else
+ #puts "nah, still #{check_block.source_blocks.size} unknowns"
end
end
+
+ #
+ # Delete this block from the graph after we have done all we can for it.
+ #
+ @graph.delete(block_nr)
end
- return got_new_block
+ #
+ # Analyze what we found out earlier.
+ #
+ to_analyze.each do |new_block, sum|
+ analyze(new_block, sum)
+ end
end
+
+ #
+ # Analyze the results of new known blocks.
+ #
+ def analyze(block_nr, block_value)
+ #puts "analyzing \##{block_nr} = #{block_value.inspect}"
+ #
+ # Do analyze_block on the block nr to see if we can resolve any check block
+ # relations from this block.
+ #
+ analyze_block(block_nr, block_value)
+ #
+ # Do aux_analyze_block on the block to see if we can resolve any aux block
+ # relations from this block.
+ #
+ analyze_aux_block(block_nr, block_value)
+ end
- def decode_chunk(blocks)
- got_new_block = false
- got_informative_block = false
+ #
+ # Analyze what we can conclude from the aux block relations and a new block.
+ #
+ def analyze_aux_block(block_nr, block_value)
+ #
+ # Remember what we want to analyze when done.
+ #
+ to_analyze = []
- blocks.clone.each do |index, block_data|
+ #
+ # If this block is a data block, check to see if it is the next to last
+ # remaining block for a known aux block.
+ #
+ # Else, check to see if we have all data blocks except one for this aux block.
+ #
+ if block_nr < @nr_of_data_blocks
+ #
+ # If we have unresolved aux data for this block.
+ #
+ if unresolved_aux_blocks_for_this_block = @aux_graph[block_nr]
+ #
+ # For each such block...
+ #
+ unresolved_aux_blocks_for_this_block.clone.each do |aux_block|
+ #
+ # If it is known.
+ #
+ if known_block = @blocks[aux_block.block_nr]
+ #
+ # Apply our new knowledge to it.
+ #
+ aux_block.apply(block_nr, block_value)
+ #
+ # Delete it from our list of unresolved blocks.
+ #
+ unresolved_aux_blocks_for_this_block.delete(aux_block)
+ #
+ # If the aux block is :finished (ie it has all but one of its data blocks
+ # accounted for).
+ #
+ if aux_block.state == :finished
+ #
+ # Record the found block to be the xor of the component blocks of the aux_block and the aux_block itself.
+ #
+ @blocks[new_block = aux_block.source_blocks.keys.first] = aux_block.xor_sum ^ known_block
- block, block_numbers = block_data
+ #
+ # Remove the aux block from the aux graph.
+ #
+ @aux_graph.delete(aux_block.block_nr)
- got_informative_block = true
+ #
+ # Remove this aux block from the found block, and if empty remove the
+ # check block list for it.
+ #
+ unresolved_aux_blocks_for_found_block = @aux_graph[new_block]
+ unresolved_aux_blocks_for_found_block.delete(aux_block)
+ @aux_graph.delete(new_block) if unresolved_aux_blocks_for_found_block.empty?
+
+ #puts "aux: \##{block_nr} = #{block_value.inspect} => \##{new_block} = #{aux_block.xor_sum.inspect}"
+
+ #
+ # Remember to analyze the results of this.
+ #
+ to_analyze << [new_block, aux_block.xor_sum]
+ else
+ #puts "aux: nah, still #{aux_block.source_blocks.size} unknowns"
+ end
+ end
+ end
+ #
+ # Delete this block from the aux graph after we have done all we can for it.
+ #
+ @aux_graph.delete(block_nr) if unresolved_aux_blocks_for_this_block.empty?
+ end
+ else
+ aux_block = @aux_graph[block_nr]
- if block_numbers.size == 1
- block_nr = block_numbers.first
+ #
+ # If the aux block is :finished (ie it has all but one of its data blocks
+ # accounted for).
+ #
+ if aux_block && aux_block.state == :finished
+ #
+ # Record the found block to be the xor of the component blocks of the aux_block and itself.
+ #
+ @blocks[new_block = aux_block.source_blocks.keys.first] = aux_block.xor_sum ^ block_value
+
+ #
+ # Remove the aux block from the aux_graph.
+ #
+ @aux_graph.delete(block_nr)
- if @blocks[block_nr].nil?
- @blocks[block_nr] = block
- got_new_block = true
- blocks.delete(index)
- end
- else
- if decode_multiple(block_data, @blocks, @nr_of_blocks)
- got_new_block = true
- blocks.delete(index)
- end
+ #
+ # Remove this aux block from the found block, and if empty remove the
+ # check block list for it.
+ #
+ unresolved_aux_blocks_for_found_block = @aux_graph[new_block]
+ unresolved_aux_blocks_for_found_block.delete(aux_block)
+ @aux_graph.delete(new_block) if unresolved_aux_blocks_for_found_block.empty?
+
+ #puts "aux: \##{block_nr} = #{block_value.inspect} => \##{new_block} = #{check_block.xor_sum.inspect}"
+
+ #
+ # Remember to analyze the results of this.
+ #
+ to_analyze << [new_block, check_block.xor_sum]
end
-
end
-
- return [got_new_block, got_informative_block]
+
+ #
+ # Analyze what we found out earlier.
+ #
+ to_analyze.each do |new_block, sum|
+ analyze(new_block, sum)
+ end
end
-
- def generate_aux_hash
- rval = Array.new(@nr_of_blocks)
+
+ #
+ # Generate the graph containing the relations between the data blocks
+ # and the aux blocks.
+ #
+ # {block nr in composite data => [data block 0, ..., data block n]}
+ #
+ def generate_aux_graph
+ rval = {}
context = Context.new
context.seed(@nr_of_data_blocks)
- 0.upto(@nr_of_data_blocks - 1) do |i|
+ 0.upto(@nr_of_data_blocks - 1) do |data_block_nr|
+
+ aux_blocks_for_this_data_block = Set.new
+ rval[data_block_nr] = aux_blocks_for_this_data_block
+
1.upto(Q) do
aux_block_nr = @nr_of_data_blocks + context.random(@nr_of_aux_blocks)
- (rval[aux_block_nr] ||= []) << i
+ aux_block = (rval[aux_block_nr] ||= AuxBlock.new(aux_block_nr))
+ aux_block << data_block_nr
+ aux_blocks_for_this_data_block << aux_block
end
end
@@ -308,6 +585,8 @@
def ensure_decode_format(requested_size)
unless defined?(@blocks)
+ @graph = {}
+ @decode_done = nil
self.concat("\000" * requested_size)
set_block_size
@nr_of_data_blocks = expand(self).size
@@ -315,10 +594,8 @@
@blocks = Array.new(@nr_of_data_blocks)
@blocks += Array.new(@nr_of_aux_blocks)
set_nr_of_blocks
- @aux_hash = generate_aux_hash
- @known_chunks = []
+ @aux_graph = generate_aux_graph
@known_nr_of_blocks = 0
- @known_block_nrs_by_seed = {}
end
end
More information about the Archipelago-submits
mailing list