""" 
<Author>
  Justin Cappos
  (inspired from a previous version by Geremy Condra)

<Start Date>
  May 15th, 2011

<Description>
  Library code that emulates the upPIR XORdatastore.   This is likely to only
  be used for testing.   There will be a C version that will be much, much 
  faster

"""

import math


def do_xor(string_a, string_b):
  """
  <Purpose>
    Produce the XOR of two equal length strings

  <Arguments>
    string_a, string_b: the strings to XOR
  
  <Side Effects>
    None

  <Exceptions>    
    ValueError if the strings are of unequal lengths 
    TypeError if the strings are not strings

  <Returns>
    The XORed result.   
  """
  if type(string_a) != str or type(string_b) != str:
    raise TypeError("do_xor called with a non-string")

  if len(string_a) != len(string_b):
    raise ValueError("do_xor requires strings of the same length")

  result = ''

  for pos in range(len(string_a)):
    # add the XOR of the two characters.   I must convert them to do so...
    result = result + chr( ord(string_a[pos]) ^ ord(string_b[pos]) )

  return result


class XORDatastore:
  """
  <Purpose>
    Class that has information for an XORdatastore.   This data structure can
    quickly XOR blocks of data that it stores.   

  <Side Effects>
    None.

  <Example Use>
    # build an XORdatastore with 16 1KB blocks.
    letterxordatastore = XORDatastore(1024, 16)

    # fill the XORdatastore with 1KB blocks with "A"-"P"
    startpos = 0
    for char in range(ord("A"), ord("Q")):
      # put 1K of those chars in...
      letterxordatastore.set_data(startpos, chr(char) * 1024) 
      startpos = startpos + 1024

    # can read data out...
    print letterxordatastore.get_data(2000, 1)
    # Should print 'B' as this is the 1 thousandth letter...

    # let's create a bitstring that uses A, C, and P.   
    bitstring = chr(int('10100000', 2)) + chr(int('00000001',2))
    xorresult = letterxordatastore.produce_xor_from_bitstring(bitstring)

    print xorresult[0]
    # this should be 'A' ^ 'C' ^ 'P' which is 'R'

  """

  # this is the private, internal storage area for data...
  _blocks = []

  # these are public so that a caller can read information about a created
  # datastore.   They should not be changed.   
  numberofblocks = None
  sizeofblocks = None
 
  def __init__(self, block_size, num_blocks):  # allocate
    """
    <Purpose>
      Allocate a place to store data for efficient XOR.   

    <Arguments>
      block_size: the size of each block.   This must be a positive int / long.
                  The value must be a multiple of 64
      
      num_blocks: the number of blocks.   This must be a positive integer

    <Exceptions>
      TypeError is raised if invalid parameters are given.

    """

    if type(block_size) != int and type(block_size) != long:
      raise TypeError("Block size must be an integer")

    if block_size <= 0:
      raise TypeError("Block size must be positive")

    if block_size %64 != 0:
      raise TypeError("Block size must be a multiple of 64")

    if type(num_blocks) != int and type(num_blocks) != long:
      raise TypeError("Number of blocks must be an integer")

    if num_blocks <= 0:
      raise TypeError("Number of blocks must be positive")


    self.numberofblocks = num_blocks
    self.sizeofblocks = block_size

    # let's create appropriately sized strings of all zero characters.   This
    # will serve as padding if there are 'gaps' in the data added.
    self._blocks = []
    for currentblocknumber in range(self.numberofblocks):
      self._blocks.append(chr(0) * self.sizeofblocks)

    

  def produce_xor_from_bitstring(self, bitstring):
    """
    <Purpose>
      Returns an XORed block from an XORdatastore.   It will always return
      a string of the size of the datastore blocks

    <Arguments>
      bitstring: a string of bits that indicates what to XOR.   The length
                 of this string must be ceil(numberofblocks / 8.0).   Extra
                 bits are ignored (e.g. if are 10 blocks, the last
                 six bits are ignored).
      
    <Exceptions>
      TypeError is raised if the bitstring is invalid

    <Returns>
      The XORed block.

    """
    if type(bitstring) != str:
      raise TypeError("bitstring must be a string")

    if len(bitstring) != math.ceil(self.numberofblocks/8.0):
      raise TypeError("bitstring is not of the correct length")

    # start with an empty string of the right size...
    currentblock = chr(0) * self.sizeofblocks
    
    # This is the block we are looking at now
    currentblocknumber = 0

    for thisbyte in bitstring:

      for bitnumber in range(0,8):

        # find the value we need to & the data with.
        bitvalue = 2**(7-bitnumber)
        
        # If it's a one...
        if ord(thisbyte) & bitvalue:
    
          # ... and we're not past the end of the string...
          if currentblocknumber < self.numberofblocks:
            # ... do the xor
            currentblock = do_xor(currentblock, self._blocks[currentblocknumber])

        # regardless, we are done with this block.
        currentblocknumber = currentblocknumber + 1

    # let's return the result!
    return currentblock
      



  def set_data(self, offset, data_to_add):
    """
    <Purpose>
      Sets the raw data in an XORdatastore.   It ignores block layout, etc.

    <Arguments>
      offset: this is a non-negative integer that must be less than the 
              numberofblocks * blocksize.   
      
      data_to_add: the string that should be added.   offset + len(data_to_add)
                must be less than the numberofblocks * blocksize.
      
    <Exceptions>
      TypeError if the arguments are the wrong type or have invalid values.

    <Returns>
      None

    """
    if type(offset) != int and type(offset) != long:
      raise TypeError("Offset must be an integer")

    if offset < 0:
      raise TypeError("Offset must be non-negative")

    if type(data_to_add) != str:
      raise TypeError("Data_to_add to XORdatastore must be a string.")

    if offset + len(data_to_add) > self.numberofblocks * self.sizeofblocks:
      raise TypeError("Offset + added data overflows the XORdatastore")

    (startblock,startoffset) = self._find_blockloc_from_offset(offset)
    (endblock, endoffset) = self._find_blockloc_from_offset(offset+len(data_to_add))
    
    # Case 1: this does not cross blocks 
    if startblock == endblock:

      # insert the string into the block...
      self._blocks[startblock] = self._blocks[startblock][:startoffset] + data_to_add + self._blocks[startblock][endoffset:]
 
      return

    # Case 2: this crosses blocks (or ends a single block)

    # we'll add the string starting with the first block...
    self._blocks[startblock] = self._blocks[startblock][:startoffset] + data_to_add[:self.sizeofblocks-startoffset]

    amountadded = self.sizeofblocks - startoffset

    # now add in the 'middle' blocks.   This is all of the blocks 
    # after the start and before the end
    for currentblock in range(startblock+1, endblock):
      self._blocks[currentblock] = data_to_add[amountadded:amountadded+self.sizeofblocks]
      amountadded = amountadded + self.sizeofblocks 


    # finally, add the end block.   Add everything left over and pad with the
    # previous block data.
    if endoffset > 0:
      self._blocks[endblock] = data_to_add[amountadded:] + self._blocks[endblock][len(data_to_add)-amountadded:]
    






  def get_data(self, offset, quantity):
    """
    <Purpose>
      Returns raw data from an XORdatastore.   It ignores block layout, etc.

    <Arguments>
      offset: this is a non-negative integer that must be less than the 
              numberofblocks * blocksize.   
      
      quantity: quantity must be a positive integer.   offset + quantity 
                must be less than the numberofblocks * blocksize.
      
    <Exceptions>
      TypeError if the arguments are the wrong type or have invalid values.

    <Returns>
      A string containing the data.

    """
    if type(offset) != int and type(offset) != long:
      raise TypeError("Offset must be an integer")

    if offset < 0:
      raise TypeError("Offset must be non-negative")

    if type(quantity) != int and type(quantity) != long:
      raise TypeError("Quantity must be an integer")

    if quantity <= 0:
      raise TypeError("Quantity must be positive")

    if offset + quantity > self.numberofblocks * self.sizeofblocks:
      raise TypeError("Quantity + offset is larger than XORdatastore")


    # Let's get the block information 
    (startblock,startoffset) = self._find_blockloc_from_offset(offset)
    (endblock, endoffset) = self._find_blockloc_from_offset(offset+quantity)

    # Case 1: this does not cross blocks
    if startblock == endblock:
      return self._blocks[startblock][startoffset:endoffset]

    # Case 2: this crosses blocks

    # we'll build up the string starting with the first block...
    currentstring = self._blocks[startblock][startoffset:]

    # now add in the 'middle' blocks.   This is all of the blocks 
    # after the start and before the end
    for currentblock in range(startblock+1, endblock):
      currentstring += self._blocks[currentblock]

    # this check is needed because we might be past the last block.
    if endoffset > 0:
      # finally, add the end block. 
      currentstring += self._blocks[endblock][:endoffset]
    
    # and return the result
    return currentstring



  def _find_blockloc_from_offset(self, offset):
    # Private helper function that translates an offset into (block, offset)
    assert(offset >=0)
    assert(offset <= self.numberofblocks * self.sizeofblocks)

    return (offset / self.sizeofblocks, offset % self.sizeofblocks)



  def __del__(self):   # deallocate
    """
    <Purpose>
      Deallocate the XORdatastore

    <Arguments>
      None

    <Exceptions>
      None

    """
    # Other implementations may need to do something here.   We need not...
    pass


