Class: Epithet::Block58

Inherits:
Object
  • Object
show all
Defined in:
lib/epithet.rb

Overview

Fixed-length Base58 codec for a fixed-size block.

Obtain codecs via Block58::build, which selects the fastest variant for the block size, an unrolled decoder for 16-byte blocks, or the generic chunked decoder otherwise.

Defined Under Namespace

Classes: Unrolled16

Constant Summary collapse

Alphabet =

= '123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'

'123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz'
POW58 =

:nodoc:

Array.new(11) { 58**_1 }.freeze

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(block_size, alphabet: Alphabet) ⇒ Block58

Create a codec for a block size in bytes.

The alphabet must be 58 distinct bytes in ascending order, so that lexicographic order agrees with numeric order.

Raises:

  • (ArgumentError) 


253
254
255
256
257
258
259
260
261
262
263
 
# File 'lib/epithet.rb', line 253

def initialize(block_size, alphabet: Alphabet)
  raise ArgumentError, 'invalid block size' unless Integer === block_size && block_size > 0
  @alphabet = alphabet.b.freeze
  raise ArgumentError, 'invalid alphabet length' unless @alphabet.bytesize == 58
  raise ArgumentError, 'alphabet not strictly ascending' unless @alphabet.bytes.each_cons(2).all? { _2 > _1 }
  @size = ((block_size * 8) / Math.log2(58)).ceil(0)
  @charsel = @alphabet.gsub(/[\^\-\\]/, '\\\\\&').freeze
  @blank = @alphabet[0] * @size
  @lut = @alphabet.each_byte.with_index.with_object("\0" * 256) { |(val, idx), lut| lut.setbyte(val, idx) }.freeze
  @max = i2s((1 << (block_size * 8)) - 1).freeze
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



244
245
246
 
# File 'lib/epithet.rb', line 244

def size
  @size
end

Class Method Details

.build(block_size) ⇒ Object

Same as ::new but may select a tuned subclass for performance.



247
 
# File 'lib/epithet.rb', line 247

def self.build(block_size, ...) = (block_size == 16 ? Unrolled16 : self).new(block_size, ...)

Instance Method Details

#i2s(int) ⇒ Object

Encode a non-negative Integer to fixed-length Base58. Truncates if int >= 58**size.



276
277
278
279
280
281
282
283
284
285
286
287
288
289
 
# File 'lib/epithet.rb', line 276

def i2s(int)
  # Using divmod+setbyte is faster than Integer#digits under YJIT,
  # and about equal in plain MRI.
  alphabet = @alphabet
  out = @blank.dup
  idx = @size - 1
  n = int
  while idx >= 0 && n > 0
    n, rem = n.divmod(58)
    out.setbyte(idx, alphabet.getbyte(rem))
    idx -= 1
  end
  out
end

#inspect ⇒ Object 



265
266
267
 
# File 'lib/epithet.rb', line 265

def inspect
  "#<#{self.class}:#{'%#016x' % (object_id << 1)} size=#{@size} alphabet=#{@alphabet}>"
end

#s2i(str) ⇒ Object

Decode a fixed-length Base58 string to an Integer. Assumes the input passes #valid?. Wraps at 58**size on the i2s round trip.



293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
 
# File 'lib/epithet.rb', line 293

def s2i(str)
  # Chunking intermediate results into 64-bit integers is ~5x faster
  # under YJIT than Horner's scheme
  #
  #   str.each_byte.inject(0) { _1 * 58 + @lut[_2] }
  #
  # at computing the inner product.
  lut = @lut
  size = @size
  pow = POW58
  acc = 0
  pos = 0
  while pos < size
    n = size - pos
    n = 10 if n > 10
    chunk = 0
    i = 0
    while i < n
      chunk = (chunk * 58) + lut.getbyte(str.getbyte(pos))
      pos += 1
      i += 1
    end
    acc = (acc * pow[n]) + chunk
  end
  acc
end

#valid?(s) ⇒ Boolean

Return true if the string is in range with the right size and alphabet.

Returns:

  • (Boolean) 


270
271
272
 
# File 'lib/epithet.rb', line 270

def valid?(s)
  String === s && s.bytesize == @size && s <= @max && s.count(@charsel) == @size
end