import sys
import binascii
import hashlib

# (un)hexlify to/from unicode, needed for Python3
unhexlify = binascii.unhexlify
hexlify = binascii.hexlify
if sys.version > '3':
    unhexlify = lambda h: binascii.unhexlify(h.encode('utf8'))
    hexlify = lambda b: binascii.hexlify(b).decode('utf8')

class Swizzler(object):
    ''' Balanced Feistel network.  Operates on bit strings of even length.  Key expansion and round function based on SHA256. '''
    def __init__(self, key=None, rounds=20):
        key = unhexlify(''.zfill(64)) if key is None else key
        K = [hashlib.sha256(key).digest()]
        for i in xrange(rounds):
            K.append(hashlib.sha256((K[-1])).digest())
        self._K = K
        self.r = rounds

    def _F(self, i, x, m):
        x = self._K[i] + unhexlify(hex(x)[2:].zfill(512))
        x = int(hashlib.sha256(x).hexdigest(), 16)
        return int(x & m)

    def E(self, b):
        assert len(b) & 1 == 0
        n = len(b)/2
        m = (1 << n) - 1
        x = int(b, 2)
        R = x & m
        L = x >> n
        for i in xrange(self.r):
            tmp = R
            R = self._F(i, R, m) ^ L
            L = tmp
        return bin((R << n) + L)[2:].zfill(2*n)
         
    def D(self, b):
        assert len(b) & 1 == 0
        n = len(b)/2
        m = (1 << n) - 1
        x = int(b, 2)
        L = x & m
        R = x >> n
        for i in reversed(xrange(self.r)):
            tmp = L
            L = self._F(i, L, m) ^ R
            R = tmp
        return bin((L << n) + R)[2:].zfill(2*n)

class BlockchainNamespace(object):
    ''' Martian namespace for transactions in the Bitcoin blockchain. '''
    def __init__(self):
        self.swizzler = Swizzler()
        self.sis = ['doz', 'mar', 'bin', 'wan', 'sam', 'lit', 'sig', 'hid', 'fid', 'lis', 'sog', 'dir', 'wac', 'sab', 'wis', 'sib', 'rig', 'sol', 'dop', 'mod', 'fog', 'lid', 'hop', 'dar', 'dor', 'lor', 'hod', 'fol', 'rin', 'tog', 'sil', 'mir', 'hol', 'pas', 'lac', 'rov', 'liv', 'dal', 'sat', 'lib', 'tab', 'han', 'tic', 'pid', 'tor', 'bol', 'fos', 'dot', 'los', 'dil', 'for', 'pil', 'ram', 'tir', 'win', 'tad', 'bic', 'dif', 'roc', 'wid', 'bis', 'das', 'mid', 'lop', 'ril', 'nar', 'dap', 'mol', 'san', 'loc', 'nov', 'sit', 'nid', 'tip', 'sic', 'rop', 'wit', 'nat', 'pan', 'min', 'rit', 'pod', 'mot', 'tam', 'tol', 'sav', 'pos', 'nap', 'nop', 'som', 'fin', 'fon', 'ban', 'por', 'wor', 'sip', 'ron', 'nor', 'bot', 'wic', 'soc', 'wat', 'dol', 'mag', 'pic', 'dav', 'bid', 'bal', 'tim', 'tas', 'mal', 'lig', 'siv', 'tag', 'pad', 'sal', 'div', 'dac', 'tan', 'sid', 'fab', 'tar', 'mon', 'ran', 'nis', 'wol', 'mis', 'pal', 'las', 'dis', 'map', 'rab', 'tob', 'rol', 'lat', 'lon', 'nod', 'nav', 'fig', 'nom', 'nib', 'pag', 'sop', 'ral', 'bil', 'had', 'doc', 'rid', 'moc', 'pac', 'rav', 'rip', 'fal', 'tod', 'til', 'tin', 'hap', 'mic', 'fan', 'pat', 'tac', 'lab', 'mog', 'sim', 'son', 'pin', 'lom', 'ric', 'tap', 'fir', 'has', 'bos', 'bat', 'poc', 'hac', 'tid', 'hav', 'sap', 'lin', 'dib', 'hos', 'dab', 'bit', 'bar', 'rac', 'par', 'lod', 'dos', 'bor', 'toc', 'hil', 'mac', 'tom', 'dig', 'fil', 'fas', 'mit', 'hob', 'har', 'mig', 'hin', 'rad', 'mas', 'hal', 'rag', 'lag', 'fad', 'top', 'mop', 'hab', 'nil', 'nos', 'mil', 'fop', 'fam', 'dat', 'nol', 'din', 'hat', 'nac', 'ris', 'fot', 'rib', 'hoc', 'nim', 'lar', 'fit', 'wal', 'rap', 'sar', 'nal', 'mos', 'lan', 'don', 'dan', 'lad', 'dov', 'riv', 'bac', 'pol', 'lap', 'tal', 'pit', 'nam', 'bon', 'ros', 'ton', 'fod', 'pon', 'sov', 'noc', 'sor', 'lav', 'mat', 'mip', 'fap']
        self.dex = ['zod', 'nec', 'bud', 'wes', 'sev', 'per', 'sut', 'let', 'ful', 'pen', 'syt', 'dur', 'wep', 'ser', 'wyl', 'sun', 'ryp', 'syx', 'dyr', 'nup', 'heb', 'peg', 'lup', 'dep', 'dys', 'put', 'lug', 'hec', 'ryt', 'tyv', 'syd', 'nex', 'lun', 'mep', 'lut', 'sep', 'pes', 'del', 'sul', 'ped', 'tem', 'led', 'tul', 'met', 'wen', 'byn', 'hex', 'feb', 'pyl', 'dul', 'het', 'mev', 'rut', 'tyl', 'wyd', 'tep', 'bes', 'dex', 'sef', 'wyc', 'bur', 'der', 'nep', 'pur', 'rys', 'reb', 'den', 'nut', 'sub', 'pet', 'rul', 'syn', 'reg', 'tyd', 'sup', 'sem', 'wyn', 'rec', 'meg', 'net', 'sec', 'mul', 'nym', 'tev', 'web', 'sum', 'mut', 'nyx', 'rex', 'teb', 'fus', 'hep', 'ben', 'mus', 'wyx', 'sym', 'sel', 'ruc', 'dec', 'wex', 'syr', 'wet', 'dyl', 'myn', 'mes', 'det', 'bet', 'bel', 'tux', 'tug', 'myr', 'pel', 'syp', 'ter', 'meb', 'set', 'dut', 'deg', 'tex', 'sur', 'fel', 'tud', 'nux', 'rux', 'ren', 'wyt', 'nub', 'med', 'lyt', 'dus', 'neb', 'rum', 'tyn', 'seg', 'lyx', 'pun', 'res', 'red', 'fun', 'rev', 'ref', 'mec', 'ted', 'rus', 'bex', 'leb', 'dux', 'ryn', 'num', 'pyx', 'ryg', 'ryx', 'fep', 'tyr', 'tus', 'tyc', 'leg', 'nem', 'fer', 'mer', 'ten', 'lus', 'nus', 'syl', 'tec', 'mex', 'pub', 'rym', 'tuc', 'fyl', 'lep', 'deb', 'ber', 'mug', 'hut', 'tun', 'byl', 'sud', 'pem', 'dev', 'lur', 'def', 'bus', 'bep', 'run', 'mel', 'pex', 'dyt', 'byt', 'typ', 'lev', 'myl', 'wed', 'duc', 'fur', 'fex', 'nul', 'luc', 'len', 'ner', 'lex', 'rup', 'ned', 'lec', 'ryd', 'lyd', 'fen', 'wel', 'nyd', 'hus', 'rel', 'rud', 'nes', 'hes', 'fet', 'des', 'ret', 'dun', 'ler', 'nyr', 'seb', 'hul', 'ryl', 'lud', 'rem', 'lys', 'fyn', 'wer', 'ryc', 'sug', 'nys', 'nyl', 'lyn', 'dyn', 'dem', 'lux', 'fed', 'sed', 'bec', 'mun', 'lyr', 'tes', 'mud', 'nyt', 'byr', 'sen', 'weg', 'fyr', 'mur', 'tel', 'rep', 'teg', 'pec', 'nel', 'nev', 'fes']
        self.sis_index = {self.sis[i]:i for i in range(len(self.sis))}        
        self.dex_index = {self.dex[i]:i for i in range(len(self.dex))} 
        
    def coords_to_vint16(self, tx_height, block_height, block_count):
        if block_count < block_height + 100:
            raise Exception("Transaction hasn't matured yet!")
        # Names expire after 262144 blocks (~5 years).
        if (block_count - block_height) >> 18 > 0:
            raise Exception("Transaction's name has expired!")
        if tx_height <= 0 or tx_height > 2097152:
            raise Exception('Transaction out of range!')   
        h = block_height
        t = tx_height
        # 8 bit names created every 2048 blocks (~once every 2 weeks).
        if h & 2047 == 0 and t == 1:
            # Names are recycled after 524288 blocks (~10 years).
            b = bin((h & 524287) >> 11)[2:].zfill(8)
        # 16 bit names created every 8 blocks.
        elif h & 7 == 0 and t == 2:
            b = bin((h & 524287) >> 3)[2:].zfill(16)  
        # 24 bit names created 32/block.
        elif (t-1) >> 5 == 0:
            b = bin(((t-1) << 19) + (h & 524287))[2:].zfill(24)
        # 32 bit names created 8192/block.
        elif (t-33) >> 13 == 0:
            b = bin(((t-33) << 19) + (h & 524287))[2:].zfill(32)
        # 40 bit names created 2097152/block.
        elif (t-8225) >> 21 == 0:
            b = bin(((t-8225) << 19) + (h & 524287))[2:].zfill(40)
        else:
            raise Exception
        # Randomized 1-1 mapping to minimize similarities between consecutive names.
        b = self.swizzler.E(b)
        return [int(b[8*i:8*(i+1)], 2) for i in range(len(b)/8)]
        
    def vint16_to_coords(self, vint16, block_count):
        b = ''.join([bin(n)[2:].zfill(8) for n in vint16])
        b = self.swizzler.D(b)
        n = int(b, 2)
        if len(b) == 8:
            t = 1
            h = n << 11
        elif len(b) == 16:
            t = 2
            h = n << 3
        elif len(b) == 24:
            t = (n >> 19) + 1
            h = n & 524287
        elif len(b) == 32:
            t = (n >> 19) + 33
            h = n & 524287
        elif len(b) == 40:
            t = (n >> 19) + 8225
            h = n & 524287
        assert block_count >= h + 100
        while (block_count - h) / 524288 > 0:
            h += 524288
        return (t, h)

    def encode(self, tx_height, block_height, block_count):
        v = self.coords_to_vint16(tx_height, block_height, block_count)
        name = []
        for i in range(0,len(v)-1,2):
            name.append(self.sis[v[i]] + self.dex[v[i+1]])
        if len(v) & 1 == 1:
            name.insert(abs(len(v)/2-1), self.dex[v[-1]])
        return '~' + '-'.join(name)

    def decode(self, name, block_count):
        v = []
        end = None
        for w in name.lstrip('~').split('-'):
            if len(w) == 3:
                end = w
            else:
                v.append(self.sis_index[w[:3]])
                v.append(self.dex_index[w[3:]])
        if end:
            v.append(self.dex_index[end])
        return self.vint16_to_coords(v, block_count)