Class: Omnizip::Algorithms::BZip2::Rle

Inherits:
Object
  • Object
show all
Defined in:
lib/omnizip/algorithms/bzip2/rle.rb

Overview

Run-Length Encoding (RLE) for BZip2

This is a BZip2-specific RLE variant that encodes runs of identical bytes. After MTF, the data often contains long runs of zeros, which RLE compresses efficiently.

BZip2 RLE encoding scheme:

  • Runs of 4-259 identical bytes are encoded as: [byte, byte, byte, byte, count-4]
  • Where count is 0-255 representing 4-259 repetitions
  • Runs < 4 are left unencoded
  • This scheme avoids ambiguity in decoding

Constant Summary collapse

MAX_RUN_LENGTH =

Maximum run length (4 + 255)

259
MIN_RUN_LENGTH =

Minimum run length for encoding

4

Instance Method Summary collapse

Instance Method Details

#decode(data) ⇒ String

Decode RLE-encoded data

Parameters:

  • data (String) —

    RLE-encoded data

Returns:

  • (String) —

    Decoded data



79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
 
# File 'lib/omnizip/algorithms/bzip2/rle.rb', line 79

def decode(data)
  return "".b if data.empty?

  # Single linear pass over the INPUT: a run marker is four
  # identical bytes followed by an extra-count byte (the old
  # decoder rescanned the growing output per byte, which made
  # decode quadratic).
  result = []
  i = 0
  n = data.bytesize

  while i < n
    byte = data.getbyte(i)
    if byte == data.getbyte(i + 1) &&
        byte == data.getbyte(i + 2) &&
        byte == data.getbyte(i + 3)
      count = data.getbyte(i + 4) || 0
      result << byte
      result << byte
      result << byte
      result << byte
      count.times { result << byte }
      i += 5
    else
      result << byte
      i += 1
    end
  end

  result.pack("C*")
end

#encode(data) ⇒ String

Encode data using BZip2 RLE

Parameters:

  • data (String) —

    Input data to encode

Returns:

  • (String) —

    RLE-encoded data



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
 
# File 'lib/omnizip/algorithms/bzip2/rle.rb', line 49

def encode(data)
  return "".b if data.empty?

  result = []
  i = 0

  while i < data.length
    byte = data.getbyte(i)
    run_length = count_run(data, i)

    if run_length >= MIN_RUN_LENGTH
      # Encode run: emit 4 copies + extra count
      extra = [run_length - MIN_RUN_LENGTH, 255].min
      4.times { result << byte }
      result << extra
      i += MIN_RUN_LENGTH + extra
    else
      # No run, emit single byte
      result << byte
      i += 1
    end
  end

  result.pack("C*")
end