module BitStruct

  # Implements access to a 'segment' of a byte string, specified by
  # offset (from bit 0) and length (in bits).
  #
  # NOTE: This is highly inefficient. If a segment is byte-aligned,
  # please use the optimized ByteSlicer class.
  #
  # NOTE: Oops! Haven't implemented the ByteSlicer, yet! :)
  #
  class BitSlicer

    attr_accessor :data

    def initialize( bit_offset, bit_length )
      raise ArgumentError if bit_offset < 0 || bit_length < 0
      @bit_offset = bit_offset
      @bit_length = bit_length
    end

    def get_bytes
      align_shift = required_shift
      bytes = get_raw_bytes

      # Step 1: Shift all bytes to the right to align bit 0
      # (in case bit_offset is not on byte border).
      BitSlicer.shift_bytes_right( bytes, align_shift )

      # Step 2: Strip highest (unused/empty) byte if necessary
      # (in case bit_length is on byte border, but bit_offset not).
      data_length = length_in_bytes
      while bytes.length > data_length
        bytes = bytes[ 1, bytes.length - 1 ]
      end

      # Step 3: Apply mask to 'highest' byte
      # (in case bit_length is not on byte border).
      bytes[ 0 ] &= highest_byte_mask
      bytes
    end

    def set_bytes( bytes )
      align_shift = required_shift

      # Step 1: Insert empty bytes to allow overflow from shifting.
      data_length = insert_length_in_bytes
      while bytes.length < data_length
        bytes.insert 0, 0x00
      end
      while bytes.length > data_length
        bytes = bytes[ 1, bytes.length - 1 ]
      end

      # Step 2: Shift all bytes to the left to align bit 0 with the 'destination postion'
      # (in case bit_offset is not on byte border).
      BitSlicer.shift_bytes_left( bytes, align_shift )

      # Step 3: Mask out unused parts of first and last byte.
      bytes[ 0 ] &= insert_first_byte_mask
      bytes[ bytes.length - 1 ] &= insert_last_byte_mask

      # Step 4: Merge existing data into first and last byte.
      bytes[ 0 ] |= masked_first_byte
      bytes[ bytes.length - 1 ] |= masked_last_byte

      # Step 5: Write back the byte data.
      set_raw_bytes bytes

      data
    end

    #private

    def set_data( idx, val )
      @data[ idx ] = val
    end

    def first_byte
      @first_byte ||= ( data.length - ( ( @bit_offset + @bit_length ) / 8.0 ).ceil )
    end

    def last_byte
      @last_byte ||= ( data.length - 1 - @bit_offset / 8 )
    end

    def length_in_bytes
      @length_in_bytes ||= ( @bit_length / 8.0 ).ceil
    end

    def insert_length_in_bytes
      @insert_length_in_bytes ||= ( ( ( @bit_offset & 7 ) + @bit_length ) / 8.0 ).ceil
    end

    def masked_first_byte
      @data[ first_byte ] & merge_first_byte_mask
    end

    def masked_last_byte
      @data[ last_byte ] & merge_last_byte_mask
    end

    def required_shift
      @bit_offset & 7
    end

    def get_raw_bytes
      raw_bytes = []
      first_byte.upto( last_byte ) do |idx|
        raw_bytes << @data[ idx ]
      end
      raw_bytes
    end

    def set_raw_bytes( raw_bytes )
      first_byte.upto( last_byte ) do |idx|
        set_data idx, raw_bytes[ idx - first_byte ]
      end
    end

    def highest_byte_mask
      return @highest_byte_mask if @highest_byte_mask
      mask_bits = ( ( @bit_length ) & 7 )
      mask_bits = 8 if mask_bits == 0
      @highest_byte_mask = ( 2 ** mask_bits ) - 1
    end

    def insert_first_byte_mask
      return @insert_first_byte_mask if @insert_first_byte_mask
      mask_bits = ( ( @bit_offset + @bit_length ) & 7 )
      mask_bits = 8 if mask_bits == 0
      @insert_first_byte_mask = ( 2 ** mask_bits ) - 1
    end

    def insert_last_byte_mask
      return @insert_last_byte_mask if @insert_last_byte_mask
      @insert_last_byte_mask = ( ( mask_bits = 0xFF ) << ( @bit_offset & 7 ) ) & 0xFF
    end

    def merge_first_byte_mask
      255 - insert_first_byte_mask
    end

    def merge_last_byte_mask
      255 - insert_last_byte_mask
    end

    def self.right_shifted( before, subject, bits )
      ( ( before << 8 | subject ) >> bits ) & 0xFF
    end

    def self.left_shifted( subject, after, bits )
      ( ( ( subject << 8 | after ) << bits ) >> 8 ) & 0xFF
    end

    def self.shift_bytes_right( bytes, bit_shift_count )
      return if bit_shift_count == 0
      raise ArgumentError if bit_shift_count < 0 || bit_shift_count > 8

      from = bytes.length - 1
      from.downto( 0 ) do |idx|
        before = idx > 0 ? bytes[ idx - 1 ] : 0
        bytes[ idx ] = BitSlicer.right_shifted( before, bytes[ idx ], bit_shift_count )
      end

      bytes
    end

    def self.shift_bytes_left( bytes, bit_shift_count )
      return if bit_shift_count == 0
      raise ArgumentError if bit_shift_count < 0 || bit_shift_count > 8

      0.upto( bytes.length - 1 ) do |idx|
        after = bytes[ idx + 1 ] || 0
        bytes[ idx ] = BitSlicer.left_shifted( bytes[ idx ], after, bit_shift_count )
      end

      bytes
    end

  end

end