Class: Huffnpuff

Inherits:
Object
  • Object
show all
Defined in:
lib/huffnpuff.rb,
lib/huffnpuff.rb,
lib/huffnpuff/version.rb

Constant Summary collapse

CMP = 
lambda { |a,b| a.length <=> b.length }
VERSION = 
"0.1.1"

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(sys, fifo, dat = []) ⇒ Huffnpuff

Returns a new instance of Huffnpuff.



84
85
86
87
88
 
# File 'lib/huffnpuff.rb', line 84

def initialize(sys, fifo, dat = [])
  @data = dat
  @fifo = fifo
  systemize!(sys)
end

Class Method Details

.get_system_string_from_histogram(ary, rat = 0.61) ⇒ Object 



41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
 
# File 'lib/huffnpuff.rb', line 41

def self.get_system_string_from_histogram(ary, rat = 0.61)
  raise "histogram array must be reverse sorted with values >= 1" unless histogram_array_valid?(ary)
  raise "parameter 2 must be between 0.1 and 0.9" unless ((rat >= 0.1) && (rat <= 0.9))
  sys = []
  top = (rat * 4096.0).to_i
  n = ary.count - 1
  tar = (ary[0] * top) >> 12
  cnt = 1
  n.times do |idx|
    if ary[idx+1] <= tar
      sys.push cnt
      cnt = 1
      tar = (ary[idx+1] * top) >> 12
    else
      cnt += 1
    end
  end
  sys.push cnt
  ary = []
  borrow = 0
  sys.each do |num|
    num -= borrow
    bin_size = 1 << (num-1).bit_length
    ary.push bin_size
    borrow = bin_size - num      
  end
  pre = ""
  if ary.count==1  # don't bother ... all same
    return "x" * (ary.first.bit_length - 1)
  end
  sys = []
  ary.each do |num|
    str = pre + "0" + "x" * (num.bit_length-1)
    pre += "1"
    sys.push str
  end
  sys.sort! &CMP
  sys.join(':')
end

.histogram_array_valid?(ary) ⇒ Boolean

Returns:

  • (Boolean) 


5
6
7
8
9
10
11
12
13
 
# File 'lib/huffnpuff.rb', line 5

def self.histogram_array_valid?(ary)
  return false if ary.empty?
  ary.each do |elm|
    return false unless elm.kind_of? Integer
    return false if elm <= 0
  end
  return false unless ary == ary.sort.reverse
  true
end

.validate_system_string(str) ⇒ Object 



15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
# File 'lib/huffnpuff.rb', line 15

def self.validate_system_string(str)
  ary = str.split(':')
  raise "singular bin not valid" if 1==ary.count
  ary.each do |bin|
    raise "empty bin definition" if bin.empty?
    raise "preamble missing: must start with 1 or 0" unless (bin[0]=='0' || bin[0]=='1')
    xmode = false
    bin.each_char do |ch|
      if xmode
        raise "illegal char following 'x': [#{ch}]" unless 'x'==ch
      else
        if ch=='x'
          xmode = true
        elsif ch=='0'
        elsif ch=='1'
        else
          raise "invalid symbol [#{ch}]"
        end
      end
    end
  end
  true
end

Instance Method Details

#get ⇒ Object

ok, we have a problem … the MSB is the preamble



159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
 
# File 'lib/huffnpuff.rb', line 159

def get
  idx = 0
  @ary.each do |ii|
    pre = @fifo.get(ii.first.length)  # not enough bits to address data
    return nil if pre.nil?
    if(pre==ii.first.to_i(2))
      if(0==ii[1]) # only one, no x's
        return @data[ii[2]]
      else
        off = @fifo.get(ii[1])
        if off.nil?
          @fifo.unget(ii[1]+ii.first.length) # not enough bits to address data
          return nil
        end
        return @data[off + ii[2]]
      end
    else # put back to try another system
      @fifo.unget(ii.first.length)  
    end
  end
  return nil    
end

#max ⇒ Object 



92
93
94
 
# File 'lib/huffnpuff.rb', line 92

def max
  @max
end

#min ⇒ Object 



89
90
91
 
# File 'lib/huffnpuff.rb', line 89

def min
  @min
end

#push(item) ⇒ Object 



138
139
140
141
 
# File 'lib/huffnpuff.rb', line 138

def push(item)
  raise "can't excede system size of #{@size}" if @data.size >= @size
  @data.push item
end

#push_each(item) ⇒ Object 



143
144
145
146
147
148
149
150
151
152
153
154
155
 
# File 'lib/huffnpuff.rb', line 143

def push_each(item)
  if item.respond_to? :each
    item.each do |elm|
      push elm
    end
  elsif item.respond_to? :each_char
    item.each_char do |ch|
      push ch
    end
  else # punt
    push item
  end
end

#size ⇒ Object 



95
96
97
 
# File 'lib/huffnpuff.rb', line 95

def size
  @size
end

#sys ⇒ Object 



99
100
101
 
# File 'lib/huffnpuff.rb', line 99

def sys()
  @sys
end

#systemize!(sys) ⇒ Object 



103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
 
# File 'lib/huffnpuff.rb', line 103

def systemize!(sys)
  @ary = []
  if sys.kind_of? String
    @sys = sys
    ary = sys.split(':')
  elsif sys.kind_of? Array
    ary = sys
    @sys = ary.join(':')
  else
    raise "imcompatible type first parameter"
  end
  self.class.validate_system_string(@sys)
  off = 0
  @min = 2 ** 10000
  @max = 0
  ary.each do |ii|
    pos = ii.index('x')
    if pos.nil?
      @ary.push [ii,0, off]
      off += 1
      sz = ii.length
      @min = sz < @min ? sz : @min
      @max = sz > @max ? sz : @max
    else
      xcount = ii.length - pos
      @ary.push [ii[(0..(pos-1))],xcount,off]
      off += 2 ** xcount
      sz = xcount + ii[(0..(pos-1))].length
      @min = sz < @min ? sz : @min
      @max = sz > @max ? sz : @max
    end
  end
  @size = off  
end