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**it }.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) 


263
264
265
266
267
268
269
270
271
272
273
274
 
# File 'lib/epithet.rb', line 263

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
  @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
  @limit = 1 << (block_size * 8)
  @max = i2s(@limit - 1).freeze
end

Instance Attribute Details

#size ⇒ Object (readonly)

Returns the value of attribute size.



254
255
256
 
# File 'lib/epithet.rb', line 254

def size
  @size
end

Class Method Details

.build(block_size) ⇒ Object

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



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

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

Instance Method Details

#i2s(int) ⇒ Object

Encode an acceptable integer to fixed-length base58.

Raises:

  • (ArgumentError) 


287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
 
# File 'lib/epithet.rb', line 287

def i2s(int)
  raise ArgumentError, 'integer out of block range' unless Integer === int && int >= 0 && int < @limit

  # 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 



276
277
278
 
# File 'lib/epithet.rb', line 276

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?, behaviour undefined if it doesn't.



306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
 
# File 'lib/epithet.rb', line 306

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. The input is read as bytes, whatever its encoding.

Returns:

  • (Boolean) 


282
283
284
 
# File 'lib/epithet.rb', line 282

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