## \file
# Define, and parse, struct/format of DEX files.
#

## \brief Manage offset
#
# The instances are initialized with a offset.  Every time an instance
# is called, it return the offset before advancing offset with specify
# size.
#
# moff = man_off(init_off)
# assert moff(5) == init_off
# assert moff() == (init_off + 5)
# assert moff() == (init_off + 5)
#
class man_off(object):
    off = None
    
    def __init__(self, off):
        self.off = off
        pass

    def __call__(self, sz=0):
        off = self.off
        self.off = off + sz
        return off
    pass


def _to_uint(data):
    v = 0
    sh = 0
    for c in data:
        v = v + (ord(c) << sh)
        sh = sh + 8
        pass
    return v


def _to_int(data):
    v = _to_uint(data)
    sz = len(data)
    if sz and ((1 << (sz * 8 - 1)) & v):
        v = -((1 << (sz * 8)) - v)
        pass
    return v


def _uleb128(data):
    sh = 0
    v = 0
    for c in data:
        cv = ord(c)
        v = v + ((cv & 0x7f) << sh)
        sh = sh + 7
        
        if cv <= 0x7f:
            break
        pass

    nbytes = sh / 7
    return v, nbytes


def _to_uleb128(v):
    assert v >= 0
    
    data = ''
    while True:
        if v > 0x7f:
            data = data + chr((v & 0x7f) | 0x80)
        else:
            data = data + chr(v & 0x7f)
            break
        v = v >> 7
        pass

    return data


def _uleb128_sz(v):
    return len(_to_uleb128(v))


def _leb128(data):
    v, sh = _uleb128(data)
    if v & (1 << (sh * 7 - 1)):
        v = -((1 << (sh * 7)) - v)
        pass
    return v, sh


def _to_leb128(v):
    data = ''
    while True:
        if v > 0x3f or v < ~0x3f:
            data = data + chr((v & 0x7f) | 0x80)
        else:
            data = data + chr(v & 0x7f)
            break
        v = v >> 7
        pass
    return data


def _leb128_sz(v):
    return len(_to_leb128(v))


def _compute_sz(o, _type):
    if hasattr(o, 'compute_size'):
        _type.compute_size(o)
        pass
    return _type.sizeof(o)


class _dex_type(object):
    pass


class _rawstr(_dex_type):
    size = None
    factor = None
    data = None
    data_size = None

    ##
    # \param size_name is dot separated attribute names from the parent.
    #
    def __init__(self, size=None, size_name=None, factor=1):
        self.size = size
        self.size_name = size_name
        self.factor = factor
        pass

    def parse(self, parent, data, off):
        obj = _rawstr(self.size, self.size_name, self.factor)
        if self.size is not None:
            size = self.size
        else:
            size = parent
            for name in self.size_name.split('.'):
                size = getattr(size, name)
                pass
            pass
        obj.data_size = size * self.factor
            
        obj.data = data[off:off + obj.data_size]
        return obj

    def compute_size(self, v):
        v.data_size = len(v.data)
        pass

    def sizeof(self, v):
        return v.data_size

    def to_str(self, v):
        return v.data
    pass

class rawstr(_rawstr):
    def __init__(self, size, factor=1):
        super(rawstr, self).__init__(size=size, factor=factor)
        pass
    pass


class rawstr_size_name(_rawstr):
    def __init__(self, size_name, factor=1):
        super(rawstr_size_name, self).__init__(size_name=size_name,
                                               factor=factor)
        pass
    pass


class tap(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        return tap()

    @staticmethod
    def sizeof(v):
        return 0

    @staticmethod
    def to_str(v):
        return ''
    pass


class uint32(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        v = _to_uint(data[off:off + 4])
        return v

    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return 4

    @staticmethod
    def to_str(v):
        return chr(v & 0xff) + chr((v >> 8) & 0xff) + chr((v >> 16) & 0xff) + \
            chr((v >> 24) & 0xff)
    pass


class uint16(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        v = _to_uint(data[off:off + 2])
        return v
    
    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return 2

    @staticmethod
    def to_str(v):
        return chr(v & 0xff) + chr((v >> 8) & 0xff)
    pass


class uint8(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        v = _to_uint(data[off:off + 1])
        return v
    
    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return 1

    @staticmethod
    def to_str(v):
        return chr(v & 0xff)
    pass


class int32(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        v = _to_int(data[off:off + 4])
        return v
    
    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return 4

    @staticmethod
    def to_str(v):
        return chr(v & 0xff) + chr((v >> 8) & 0xff) + chr((v >> 16) & 0xff) + \
            chr((v >> 24) & 0xff)
    pass


class int16(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        v = _to_int(data[off:off + 2])
        return v

    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return 2

    @staticmethod
    def to_str(v):
        return chr(v & 0xff) + chr((v >> 8) & 0xff)
    pass


class uleb128(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        v, sh = _uleb128(data[off:off + 5])
        return v

    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return _uleb128_sz(v)

    @staticmethod
    def to_str(v):
        return _to_uleb128(v)
    pass


class leb128(_dex_type):
    @staticmethod
    def parse(parent, data, off):
        v, sh = _leb128(data[off:off + 5])
        return v

    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return _leb128_sz(v)

    @staticmethod
    def to_str(v):
        return _to_leb128(v)
    pass


class auto_align(_dex_type):
    bits = None
    
    def __init__(self, bits):
        self.bits = bits
        pass

    def recompute_align(self, off):
        mask = (1 << self.bits) - 1
        padding_sz = ((off + mask) & ~mask) - off
        return padding_sz
    
    def parse(self, parent, data, off):
        return self.recompute_align(off)

    @staticmethod
    def compute_size(v):
        pass
    
    @staticmethod
    def sizeof(v):
        return v

    @staticmethod
    def to_str(v):
        return '\x00' * v
    pass


def _get_sz(o):
    if isinstance(o, relocatable):
        return o.data_size
    return o.__class__.sizeof(o)


## \biref Associate objects from two set of objects.
#
class _objs_asso(_dex_type):
    left = None
    left_ref = None
    right = None
    right_ref = None
    
    ## \brief Update references for a element pair from left and right.
    #
    # This method must be called by derivation to associate a pair of
    # elements.
    #
    def _update_refs(self, left_elt, right_elt):
        lref = getattr(left_elt, self.left_ref)
        if not isinstance(right_elt, lref.target_path):
            raise TypeError, 'invalid target_path in left %s' % (repr(le))
        
        rref = getattr(right_elt, self.right_ref)
        if not isinstance(left_elt, rref.target_path):
            raise TypeError, 'invalid target_path in right %s' % (repr(re))
        
        new_lref = ref(lref.target_path)
        new_lref.target = right_elt
        setattr(left_elt, self.left_ref, new_lref)

        new_rref = ref(rref.target_path)
        new_rref.target = left_elt
        setattr(right_elt, self.right_ref, new_rref)
        pass
    
    ## \brief Assocate elements from left list to a respective right element.
    #
    # This method must be called before linking dependencies.
    #
    def build_associations(self, left, right):
        raise NotImplementedError, 'build_associations is not implemented'

    def parse(self, parent, data, off):
        return self

    def sizeof(self, obj):
        return 0

    def to_str(self):
        return ''

    @staticmethod
    def compute_size(self):
        pass

    def children(self):
        return []
    pass


## \brief One to one association.
#
# Associate nth element from left sequence to nth element in right
# sequence.
#
class one2one(_objs_asso):
    def __init__(self, left, left_ref, right, right_ref):
        self.left = left
        self.left_ref = left_ref
        self.right = right
        self.right_ref = right_ref
        pass

    ## \brief Associate elements from left list to elements from right list
    #
    def build_associations(self, left, right):
        assert len(left) == len(right)
        for le, re in map(None, left, right):
            self._update_refs(le, re)
            pass
        pass
    pass


class relocatable(_dex_type):
    data_size = None

    @staticmethod
    def parse(parent, data, off):
        pass

    @staticmethod
    def sizeof(v):
        return v.data_size

    def to_str(self):
        pass

    def compute_size(self):
        pass

    def children(self):
        raise NotImplementedError, \
            '%s: does not implement children' % (self.__class__.__name__)
    pass


class null_relocatable(relocatable):
    back_type = None
    pass


## \brief Implicit reference to a target.
#
# It is a placeholder for storing relationship defined by an association.
#
class ref(_dex_type):
    target_path = None

    def __init__(self, target_path=None):
        self.target_path = target_path
        pass

    @staticmethod
    def parse(parent, data, off):
        pass

    @staticmethod
    def sizeof(v):
        return 0

    @staticmethod
    def compute_size(self):
        pass

    @staticmethod
    def to_str(child):
        return ''

    def get_value(self, parents):
        pass

    def children(self):
        return []
    pass


## \brief Reference to a value from a given path.
#
class value_ref(ref):
    def get_value(self, parents):
        from paraspace.dex_deptracker import _resolve_name_path
        from paraspace.dex_deptracker import _dex_tree_get_child
        
        pparts = self.target_path.split('.')
        clazz_name = pparts[0]
        clazz, dummy = _resolve_name_path(clazz_name)
        
        rev_parents = list(parents)
        rev_parents.reverse()
        
        for parent in rev_parents:
            if isinstance(parent, clazz):
               break
            pass
        else:
            raise ValueError, 'can not find %s' % (self.target_path)

        attr_path = '.'.join(pparts[1:])
        value = _dex_tree_get_child(parent, attr_path)
        return value

    def set_value(self, value, parents):
        from paraspace.dex_deptracker import _resolve_name_path
        from paraspace.dex_deptracker import _dex_tree_get_child
        
        pparts = self.target_path.split('.')
        clazz_name = pparts[0]
        clazz, dummy = _resolve_name_path(clazz_name)
        
        rev_parents = list(parents)
        rev_parents.reverse()
        
        for parent in rev_parents:
            if isinstance(parent, clazz):
               break
            pass
        else:
            raise ValueError, 'can not find %s' % (self.target_path)

        attr_path = '.'.join(pparts[1:])
        _dex_tree_set_child(parent, attr_path, value)
        pass
    pass


class array(relocatable):
    count_name = None
    child_type = None
    items = None

    def __init__(self, count_name, child_type):
        super(array, self).__init__()
        self.count_name = count_name
        self.child_type = child_type
        pass

    def parse(self, parent, data, off):
        nitem = parent
        for name in self.count_name.split('.'):
            nitem = getattr(nitem, name)
            pass
        obj = self.parse_nitem(parent, data, off, nitem)
        return obj

    def parse_nitem(self, parent, data, off, nitem):
        moff = man_off(off)

        obj = self.__class__(self.count_name, self.child_type)
        
        def parse():
            item = obj.child_type.parse(parent, data, moff())
            item_sz = obj.child_type.sizeof(item)
            moff(item_sz)
            return item
        
        items = [parse() for i in range(nitem)]
        
        obj.items = items
        obj.data_size = moff() - off
        return obj

    @staticmethod
    def compute_size(self):
        sizes = [_compute_sz(item, self.child_type)
                 for item in self.items]
        size = sum(sizes)
        self.data_size = size
        pass

    @staticmethod
    def to_str(self):
        to_str = self.child_type.to_str
        strs = [to_str(item) for item in self.items]
        return ''.join(strs)

    def children(self):
        return ('items',)
    pass


class array_sorted(array):
    pass


class composite(relocatable):
    child_names = None

    def __init__(self):
        for child_name in self.child_names:
            setattr(self, child_name, None)
            pass
        pass

    def parse_child(self, child_name, data, off):
        child_clazz = getattr(self.__class__, child_name)
        child = child_clazz.parse(self, data, off)
        setattr(self, child_name, child)
        pass

    @classmethod
    def parse(clazz, parent, data, off):
        moff = man_off(off)
        obj = clazz()

        for child_name in clazz.child_names:
            obj.parse_child(child_name, data, moff())
            child = getattr(obj, child_name)
            child_clazz = getattr(obj.__class__, child_name)
            child_sz = child_clazz.sizeof(child)
            moff(child_sz)
            pass

        obj.data_size = moff() - off
        return obj

    def compute_size(self):
        children = [(getattr(self, child_name),
                     getattr(self.__class__, child_name))
                    for child_name in self.children()]
        child_sizes = [_compute_sz(child, child_type)
                       for child, child_type in children]
        self.data_size = sum(child_sizes)
        pass

    def to_str(self):
        child_clazzs = [getattr(self.__class__, child_name)
                        for child_name in self.children()]
        children = [getattr(self, child_name)
                    for child_name in self.children()]
        child_strs = map(lambda child_clazz, child: \
                             child_clazz.to_str(child),
                         child_clazzs, children)
        return ''.join(child_strs)

    def children(self):
        return self.child_names
    pass


class cond(relocatable):
    condition = None
    child_type = None
    value = None
    is_true = None
    
    def __init__(self, cond, child_type):
        self.condition = cond
        self.child_type = child_type
        pass

    def parse(self, parent, data, off):
        if self.condition(parent, data, off):
            value = self.child_type.parse(parent, data, off)
            is_true = True
        else:
            value = None
            is_true = False
            pass

        obj = cond(self.condition, self.child_type)
        obj.value = value
        obj.data_size = self.sizeof(obj)
        obj.is_true = is_true
        
        return obj

    def sizeof(self, v):
        if v.value is None:
            return 0
        return self.child_type.sizeof(v.value)

    @staticmethod
    def compute_size(self):
        if self.is_true:
            self.data_size = _compute_sz(self.value, self.child_type)
        else:
            self.data_size = 0
            pass
        pass

    @staticmethod
    def to_str(self):
        if self.value is None:
            return ''

        data = self.child_type.to_str(self.value)
        return data

    def children(self):
        if self.is_true:
            return ('value',)
        return ()
    pass


class switch(relocatable):
    selector = None
    map = None
    child_type = None
    value = None
    
    _parent = None
    
    def __init__(self, selector, map):
        self.selector = selector
        self.map = map
        pass

    def switch_key(self, parent):
        selector = self.selector
        sel_value = parent
        for name in selector.split('.'):
            sel_value = getattr(sel_value, name)
            pass
        return sel_value
    
    def _get_child_type(self, parent):
        sel_value = self.switch_key(parent)

        child_type = self.map[sel_value]
        return child_type
    
    def parse(self, parent, data, off):
        child_type = self._get_child_type(parent)
        value = child_type.parse(parent, data, off)

        obj = switch(self.selector, self.map)
        obj.value = value
        obj.child_type = child_type
        obj.data_size = self.sizeof(obj)
        obj._parent = parent
        return obj
    
    @staticmethod
    def sizeof(v):
        return v.child_type.sizeof(v.value)

    @staticmethod
    def compute_size(self):
        self.data_size = _compute_sz(self.value, self.child_type)
        pass

    @staticmethod
    def to_str(self):
        data = self.child_type.to_str(self.value)
        return data

    def children(self):
        key = self.switch_key(self._parent)
        return (repr(key),)
    pass


class abs_value(_dex_type):
    value = None
    
    def __init__(self, value):
        self.value = value
        pass

    def parse(self, parse, data, off):
        return self.value
    
    @staticmethod
    def compute_size(v):
        pass

    def sizeof(self, v):
        return 0
    
    @staticmethod
    def to_str(self):
        return ''

    def children(self):
        return ()
    pass


## \brief Make a dependency to a depend-on for back type.
#
# Depend-on is the object that the back type is supposed to point to.
# Back type of a depend must be not a composite type while depend-on
# must be.
#
class depend(null_relocatable):
    depend_on = None
    
    def __init__(self, depend_on):
        self.depend_on = depend_on
        pass

    def __call__(self, back_type):
        assert type(back_type) != type or not issubclass(back_type, composite)
        self.back_type = back_type
        return self

    def parse(self, parent, data, off):
        v = self.back_type.parse(parent, data, off)
        return v

    def sizeof(self, v):
        from paraspace.dex_deptracker import _resolve_name_path
        from paraspace.dex_deptracker import _skip_marker_clazz
        
        depon_clazz, dummy = _resolve_name_path(self.depend_on)
        depon_clazz = _skip_marker_clazz(depon_clazz)
        if type(depon_clazz) == type and \
                isinstance(v, depon_clazz):
            v = v.data_offset
        elif type(depon_clazz) != type and \
                isinstance(v, depon_clazz.__class__):
            v = v.data_offset
            pass
        v = self.back_type.sizeof(v)
        return v

    def compute_size(self, child):
        _compute_sz(child, self.back_type)
        pass

    def to_str(self, child):
        return self.back_type.to_str(child)
    pass


def _set_name_path_name(parent, name, obj):
    if isinstance(parent, (list, dict)):
        key = eval(name)
        parent[key] = obj
        return
    setattr(parent, name, obj)
    pass


class depend_off(depend):
    def compute_size(self, child):
        pass

    def sizeof(self, child):
        if isinstance(child, composite):
            return self.back_type.sizeof(child.data_offset)
        return self.back_type.sizeof(child)
    pass


class depend_off_rel(depend):
    relative_to = None
    _depon2_log = {}

    def __init__(self, relative_to, depend_on):
        super(depend_off_rel, self).__init__(depend_on)
        self.relative_to = relative_to
        pass

    def parse(self, parent, data, off):
        v = super(depend_off_rel, self).parse(parent, data, off)
        return v

    def compute_size(self, child):
        pass

    def sizeof(self, child):
        if isinstance(child, composite):
            pivot = self._depon2_log[child] # depon2
            off_diff = child.data_offset - pivot.data_offset
            return self.back_type.sizeof(off_diff)
        return self.back_type.sizeof(child)
    pass


class depend_idx(depend):
    def sizeof(self, v):
        from paraspace.dex_deptracker import _resolve_name_path
        from paraspace.dex_deptracker import _skip_marker_clazz
        
        depon_clazz, dummy = _resolve_name_path(self.depend_on)
        depon_clazz = _skip_marker_clazz(depon_clazz)
        do_child_clazz = depon_clazz.child_type # depon_clazz must be an array
        
        if type(do_child_clazz) == type and \
                isinstance(v, do_child_clazz):
            v = v.data_idx
        elif type(do_child_clazz) != type and \
                isinstance(v, do_child_clazz.__class__):
            v = v.data_idx
            pass
        v = self.back_type.sizeof(v)
        return v

    def compute_size(self, child):
        pass

    def sizeof(self, child):
        if isinstance(child, composite):
            return self.back_type.sizeof(child.data_idx)
        return self.back_type.sizeof(child)
    pass


class _DEX_header(composite):
    magic = rawstr(8)
    checksum = uint32
    signature = rawstr(20)
    fileSize = uint32
    headerSize = uint32
    endianTag = uint32
    linkSize = uint32
    linkOff = uint32
    mapOff = uint32
    stringIdsSize = uint32
    stringIdsOff = uint32
    typeIdsSize = uint32
    typeIdsOff = uint32
    protoIdsSize = uint32
    protoIdsOff = uint32
    fieldIdsSize = uint32
    fieldIdsOff = uint32
    methodIdsSize = uint32
    methodIdsOff = uint32
    classDefsSize = uint32
    classDefsOff = uint32
    dataSize = uint32
    dataOff = uint32
    
    child_names = \
        'magic checksum signature fileSize headerSize endianTag ' \
        'linkSize linkOff mapOff stringIdsSize stringIdsOff typeIdsSize ' \
        'typeIdsOff protoIdsSize protoIdsOff fieldIdsSize fieldIdsOff ' \
        'methodIdsSize methodIdsOff classDefsSize classDefsOff ' \
        'dataSize dataOff'.split()
    pass


class _DEX_MapItem(composite):
    type = uint16
    unused = uint16
    size = uint32
    offset = uint32

    types = {
        0x0000: 'kDexTypeHeaderItem',
        0x0001: 'kDexTypeStringIdItem',
        0x0002: 'kDexTypeTypeIdItem',
        0x0003: 'kDexTypeProtoIdItem',
        0x0004: 'kDexTypeFieldIdItem',
        0x0005: 'kDexTypeMethodIdItem',
        0x0006: 'kDexTypeClassDefItem',
        0x1000: 'kDexTypeMapList',
        0x1001: 'kDexTypeTypeList',
        0x1002: 'kDexTypeAnnotationSetRefList',
        0x1003: 'kDexTypeAnnotationSetItem',
        0x2000: 'kDexTypeClassDataItem',
        0x2001: 'kDexTypeCodeItem',
        0x2002: 'kDexTypeStringDataItem',
        0x2003: 'kDexTypeDebugInfoItem',
        0x2004: 'kDexTypeAnnotationItem',
        0x2005: 'kDexTypeEncodedArrayItem',
        0x2006: 'kDexTypeAnnotationsDirectoryItem'
        }

    name_to_types = dict([(_name, _typenum)
                          for _typenum, _name in types.items()])
    
    child_names = \
        'type unused size offset'.split()
    pass


class _DEX_MapItemBlock(composite):
    padding = auto_align(2)
    num = uint32
    items = array('num', _DEX_MapItem)

    child_names = 'padding num items'.split()
    pass


class _DEX_StringId(composite):
    stringDataOff = depend_off('_DEX_StringDataItem')(uint32)

    child_names = ('stringDataOff',)

    def __cmp__(self, other):
        assert isinstance(other, _DEX_StringId)
        assert isinstance(self.stringDataOff, _DEX_StringDataItem)
        assert isinstance(other.stringDataOff, _DEX_StringDataItem)

        return cmp(self.stringDataOff.data.data, other.stringDataOff.data.data)
    pass


class _DEX_TypeId(composite):
    descriptorIdx = depend_idx('DEXFile.stringIds')(uint32)

    child_names = ('descriptorIdx',)

    def __cmp__(self, other):
        assert isinstance(other, _DEX_TypeId)
        assert isinstance(self.descriptorIdx, _DEX_StringId)
        assert isinstance(other.descriptorIdx, _DEX_StringId)

        return cmp(self.descriptorIdx, other.descriptorIdx)
    pass


class _DEX_ProtoId(composite):
    shortyIdx = depend_idx('DEXFile.stringIds')(uint32)
    returnTypeIdx = depend_idx('DEXFile.typeIds')(uint32)
    parametersOff = uint32
    parametersOffRef = cond((lambda parent, data, off: parent.parametersOff),
                            depend_off('_DEX_TypeList')
                            (value_ref('_DEX_ProtoId.parametersOff')))
    
    child_names = 'shortyIdx returnTypeIdx parametersOff ' \
        'parametersOffRef'.split()

    ## \brief Compare two linked _DEX_ProtoId instances.
    def __cmp__(self, other):
        assert isinstance(other, _DEX_ProtoId)
        assert isinstance(self.returnTypeIdx, _DEX_TypeId)
        assert isinstance(other.returnTypeIdx, _DEX_TypeId)

        r = cmp(self.returnTypeIdx, other.returnTypeIdx)
        if r != 0:
            return r
        if not self.parametersOffRef.is_true:
            return -1
        if not other.parametersOffRef.is_true:
            return 1
        
        tlist0 = self.parametersOffRef.value.typeItems.items
        tlist1 = other.parametersOffRef.value.typeItems.items
        for param0, param1 in map(None, tlist0, tlist1):
            if not (param0 and param1):
                break
            
            r = cmp(param0.typeIdx, param1.typeIdx)
            if r != 0:
                return r
            pass

        return cmp(len(tlist0), len(tlist1))
    pass


class _DEX_FieldId(composite):
    classIdx = depend_idx('DEXFile.typeIds')(uint16)
    typeIdx = depend_idx('DEXFile.typeIds')(uint16)
    nameIdx = depend_idx('DEXFile.stringIds')(uint32)

    child_names = 'classIdx typeIdx nameIdx'.split()

    def __cmp__(self, other):
        assert isinstance(other, _DEX_FieldId)
        assert isinstance(self.classIdx, _DEX_TypeId)
        assert isinstance(other.classIdx, _DEX_TypeId)

        r = cmp(self.classIdx, other.classIdx)
        if r != 0:
            return r
        r = cmp(self.nameIdx, other.nameIdx)
        if r != 0:
            return r
        r = cmp(self.typeIdx, other.typeIdx)
        return r
    pass


class _DEX_MethodId(composite):
    classIdx = depend_idx('DEXFile.typeIds')(uint16)
    protoIdx = depend_idx('DEXFile.protoIds')(uint16)
    nameIdx = depend_idx('DEXFile.stringIds')(uint32)

    child_names = 'classIdx protoIdx nameIdx'.split()
    
    def __cmp__(self, other):
        assert isinstance(other, _DEX_MethodId)
        assert isinstance(self.classIdx, _DEX_TypeId)
        assert isinstance(other.classIdx, _DEX_TypeId)

        r = cmp(self.classIdx, other.classIdx)
        if r != 0:
            return r
        r = cmp(self.nameIdx, other.nameIdx)
        if r != 0:
            return r
        r = cmp(self.typeIdx, other.protoIdx)
        return r
    pass


class _DEX_ClassDef(composite):
    classIdx = depend_idx('DEXFile.typeIds')(uint32)
    accessFlags = uint32
    superclassIdx = depend_idx('DEXFile.typeIds')(uint32)
    interfacesOff = uint32
    interfacesOffRef = cond((lambda parent, data, off: parent.interfacesOff),
                            depend_off('_DEX_TypeList')
                            (value_ref('_DEX_ClassDef.interfacesOff')))
    sourceFileIdx = depend_idx('DEXFile.stringIds')(uint32)
    annotationsOff = uint32
    annotationsOffRef = cond((lambda parent, data, off: parent.annotationsOff),
                             depend_off('_DEX_AnnotationsDirectoryItem')
                             (value_ref('_DEX_ClassDef.annotationsOff')))
    classDataOff = uint32
    classDataOffRef = cond((lambda parent, data, off: parent.classDataOff),
                           depend_off('_DEX_ClassData')
                           (value_ref('_DEX_ClassDef.classDataOff')))
    staticValuesOff = uint32
    staticValuesOffRef = cond((lambda parent, data, off:
                                   parent.staticValuesOff),
                              depend_off('_DEX_EncodedArrayItem')
                              (value_ref('_DEX_ClassDef.staticValuesOff')))
    
    child_names = \
        'classIdx accessFlags superclassIdx interfacesOff interfacesOffRef ' \
        'sourceFileIdx annotationsOff annotationsOffRef ' \
        'classDataOff classDataOffRef staticValuesOff ' \
        'staticValuesOffRef'.split()
    pass


class _DEX_ClassDataHeader(composite):
    staticFieldsSize = uleb128
    instanceFieldsSize = uleb128
    directMethodsSize = uleb128
    virtualMethodsSize = uleb128

    child_names = \
        'staticFieldsSize instanceFieldsSize directMethodsSize ' \
        'virtualMethodsSize'.split()
    pass


class _DEX_Field(composite):
    fieldIdx = depend_idx('DEXFile.fieldIds')(uleb128)
    accessFlags = uleb128

    child_names = 'fieldIdx accessFlags'.split()
    pass


class _DEX_Method(composite):
    methodIdx = depend_idx('DEXFile.methodIds')(uleb128)
    accessFlags = uleb128
    codeOff = uleb128
    codeOffRef = cond((lambda parent, data, off: parent.codeOff),
                      depend_off('_DEX_Code')
                      (value_ref('_DEX_Method.codeOff')))

    child_names = 'methodIdx accessFlags codeOff codeOffRef'.split()
    pass


class _DEX_ClassData(composite):
    header = _DEX_ClassDataHeader
    staticFields = array('header.staticFieldsSize', _DEX_Field)
    instanceFields = array('header.instanceFieldsSize', _DEX_Field)
    directMethods = array('header.directMethodsSize', _DEX_Method)
    virtualMethods = array('header.virtualMethodsSize', _DEX_Method)

    child_names = \
        'header ' \
        'staticFields instanceFields directMethods virtualMethods'.split()
    pass


class _DEX_TypeList_typeid(composite):
    typeIdx = depend_idx('DEXFile.typeIds')(uint16)

    child_names = ('typeIdx',)
    pass


class _DEX_TypeList(composite):
    num = uint32
    typeItems = array('num', _DEX_TypeList_typeid)

    child_names = 'num typeItems'.split()
    pass


class _DEX_TypeList_align(composite):
    padding = auto_align(2)     # 2 bits alignment
    value = _DEX_TypeList
    
    child_names = 'padding value'.split()
    pass


class _DEX_Try(composite):
    startAddr = uint32
    insnCount = uint16
    handlerOff = depend_off_rel('_DEX_Code.handlers_size',
                                '_DEX_Catch')(uint16)

    child_names = 'startAddr insnCount handlerOff'.split()
    pass


class _DEX_CatchHandler(composite):
    typeIdx = depend_idx('DEXFile.typeIds')(uleb128)
    address = uleb128

    child_names = 'typeIdx address'.split()
    pass


class _DEX_CatchAllHandler(composite):
    address = uleb128

    child_names = 'address'.split()
    pass


class _DEX_Catch(composite):
    size = leb128
    handlers = array('count', _DEX_CatchHandler)
    catchAllHandler = cond((lambda parent, data, off: parent.catchesAll),
                           _DEX_CatchAllHandler)

    child_names = 'size handlers catchAllHandler'.split()

    @property
    def catchesAll(self):
        return self.size <= 0

    @property
    def count(self):
        if self.size < 0:
            return -self.size
        return self.size
    pass


class _DEX_Code(composite):
    registersSize = uint16
    insSize = uint16
    outsSize = uint16
    triesSize = uint16
    debugInfoOff = depend_off('_DEX_DebugInfoItem')(uint32)
    insnsSize = uint32
    insns = rawstr_size_name('insnsSize', 2)
    
    _has_tries = lambda parent, data, off: parent.triesSize > 0
    
    padding = cond(_has_tries, auto_align(2))
    try_items = cond(_has_tries,
                     array('triesSize', _DEX_Try))
    
    handlers_size = cond(_has_tries, uleb128)
    catch_handler_items = cond(_has_tries,
                               array('handlers_size.value', _DEX_Catch))

    padding2 = auto_align(2)

    child_names = \
        'registersSize insSize outsSize triesSize debugInfoOff ' \
        'insnsSize insns padding try_items handlers_size ' \
        'catch_handler_items padding2'.split()
    pass


class _DEX_AnnotationSetItem_anno_item(composite):
    offset = depend_off('_DEX_AnnotationItem')(uint32)

    child_names = ('offset',)
    pass


class _DEX_AnnotationSetItem(composite):
    size = uint32
    annotationOffs = array('size', _DEX_AnnotationSetItem_anno_item)

    child_names = 'size annotationOffs'.split()
    pass


class _DEX_FieldAnnotationsItem(composite):
    fieldIdx = depend_idx('DEXFile.fieldIds')(uint32)
    annotationsOff = uint32
    annotationsOffRef = cond((lambda parent, data, off: parent.annotationsOff),
                             depend_off('_DEX_AnnotationSetItem')
                             (value_ref('_DEX_FieldAnnotationsItem.'
                                        'annotationsOff')))
    
    child_names = 'fieldIdx annotationsOff annotationsOffRef'.split()

    def __cmp__(self, other):
        assert isinstance(other, _DEX_FieldAnnotationsItem)
        assert isinstance(self.fieldIdx, _DEX_FieldId)
        assert isinstance(other.fieldIdx, _DEX_FieldId)
        
        return cmp(self.fieldIdx, other.fieldIdx)
    pass


class _DEX_MethodAnnotationsItem(composite):
    methodIdx = depend_idx('DEXFile.methodIds')(uint32)
    annotationsOff = uint32
    annotationsOffRef = cond((lambda parent, data, off: parent.annotationsOff),
                             depend_off('_DEX_AnnotationSetItem')
                             (value_ref('_DEX_MethodAnnotationsItem.'
                                        'annotationsOff')))

    child_names = 'methodIdx annotationsOff annotationsOffRef'.split()

    def __cmp__(self, other):
        assert isinstance(other, _DEX_MethodAnnotationsItem)
        assert isinstance(self.methodIdx, _DEX_MethodId)
        assert isinstance(other.methodIdx, _DEX_MethodId)
        
        return cmp(self.methodIdx, other.methodIdx)
    pass


class _DEX_ParameterAnnotationsItem(composite):
    methodIdx = depend_idx('DEXFile.methodIds')(uint32)
    annotationsOff = uint32
    annotationsOffRef = cond((lambda parent, data, off: parent.annotationsOff),
                             depend_off('_DEX_AnnotationSetItem')
                             (value_ref('_DEX_ParameterAnnotationsItem.'
                                        'annotationsOff')))

    child_names = 'methodIdx annotationsOff annotationsOffRef'.split()

    def __cmp__(self, other):
        assert isinstance(other, _DEX_ParameterAnnotationsItem)
        assert isinstance(self.methodIdx, _DEX_MethodId)
        assert isinstance(other.methodIdx, _DEX_MethodId)
        
        return cmp(self.methodIdx, other.methodIdx)
    pass


class _DEX_AnnotationsDirectoryItem(composite):
    classAnnotationsOff = uint32
    classAnnotationsOffRef = cond((lambda parent, data, off:
                                       parent.classAnnotationsOff),
                             depend_off('_DEX_AnnotationSetItem')
                             (value_ref('_DEX_AnnotationsDirectoryItem.'
                                        'classAnnotationsOff')))
    fieldsSize = uint32
    methodsSize = uint32
    parametersSize = uint32
    
    fieldAnnotationsItems = array_sorted('fieldsSize',
                                         _DEX_FieldAnnotationsItem)
    methodAnnotationsItems = array_sorted('methodsSize',
                                          _DEX_MethodAnnotationsItem)
    parameterAnnotationsItems = array_sorted('parametersSize',
                                             _DEX_ParameterAnnotationsItem)

    child_names = 'classAnnotationsOff classAnnotationsOffRef ' \
        'fieldsSize methodsSize ' \
        'parametersSize fieldAnnotationsItems methodAnnotationsItems ' \
        'parameterAnnotationsItems'.split()
    pass


class _DEX_AnnotationArray(composite):
    size = uleb128
    # annotations = array('size', _DEX_AnnotationMember_noname)

    child_names = 'size annotations'.split()
    pass


##
#
# \see createAnnotationMember() in dalvik/vm/reflect/Annotation.c
#
class _DEX_AnnotationMember_noname(composite):
    #
    # Constants from DexFile.h
    #
    kDexAnnotationByte = 0x00
    kDexAnnotationShort = 0x02
    kDexAnnotationChar = 0x03
    kDexAnnotationInt = 0x04
    kDexAnnotationLong = 0x06
    kDexAnnotationFloat = 0x10
    kDexAnnotationDouble = 0x11
    kDexAnnotationString = 0x17
    kDexAnnotationType = 0x18
    kDexAnnotationField = 0x19
    kDexAnnotationMethod = 0x1a
    kDexAnnotationEnum = 0x1b
    kDexAnnotationArray = 0x1c
    kDexAnnotationAnnotation = 0x1d
    kDexAnnotationNull = 0x1e
    kDexAnnotationBoolean = 0x1f
    
    kDexAnnotationValueTypeMask = 0x1f
    kDexAnnotationValueArgShift = 5

    valueType = uint8
    value_map = {
        kDexAnnotationByte: rawstr_size_name('value_width'),
        kDexAnnotationShort: rawstr_size_name('value_width'),
        kDexAnnotationChar: rawstr_size_name('value_width'),
        kDexAnnotationInt: rawstr_size_name('value_width'),
        kDexAnnotationLong: rawstr_size_name('value_width'),
        kDexAnnotationFloat: rawstr_size_name('value_width'),
        kDexAnnotationDouble: rawstr_size_name('value_width'),
        kDexAnnotationString: rawstr_size_name('value_width'),
        kDexAnnotationType: rawstr_size_name('value_width'),
        kDexAnnotationMethod: rawstr_size_name('value_width'),
        kDexAnnotationField: rawstr_size_name('value_width'),
        kDexAnnotationEnum: rawstr_size_name('value_width'),
        kDexAnnotationNull: abs_value(0),
        kDexAnnotationBoolean: abs_value(0), # width != 0
        kDexAnnotationArray: _DEX_AnnotationArray,
        # kDexAnnotationAnnotation: _DEX_AnnotationItem_novisibility
        }
    value = switch('vtype', value_map)

    child_names = 'valueType value'.split()

    @property
    def vtype(self):
        vtype = self.valueType & self.kDexAnnotationValueTypeMask
        return vtype
    
    @property
    def width(self):
        width = self.valueType >> self.kDexAnnotationValueArgShift
        return width

    @property
    def value_width(self):
        width = self.valueType >> self.kDexAnnotationValueArgShift
        return width + 1
    pass


class _DEX_AnnotationMember(_DEX_AnnotationMember_noname):
    nameIdx = depend_idx('DEXFile.stringIds')(uleb128)
    
    child_names = 'nameIdx valueType value'.split()

    def __cmp__(self, other):
        assert isinstance(other, _DEX_AnnotationMember)
        assert isinstance(self.nameIdx, _DEX_StringId)
        assert isinstance(other.nameIdx, _DEX_StringId)
        
        return cmp(self.nameIdx, other.nameIdx)
    pass


_DEX_AnnotationArray.annotations = array('size', _DEX_AnnotationMember_noname)


## \brief Annotation item
#
# \see processEncodedAnnotation() in dalvik/vm/reflect/Annotation.c
#
class _DEX_AnnotationItem_novisibility(composite):
    typeIdx = depend_idx('DEXFile.typeIds')(uleb128)
    size = uleb128
    members = array_sorted('size', _DEX_AnnotationMember)

    child_names = 'typeIdx size members'.split()
    
    kDexVisibilityBuild = 0x00
    kDexVisibilityRuntime = 0x01
    kDexVisibilitySystem = 0x02

    def __cmp__(self, other):
        assert isinstance(other, _DEX_AnnotationItem_novisibility)
        assert isinstance(self.typeIdx, _DEX_TypeId)
        assert isinstance(other.typeIdx, _DEX_TypeId)

        return cmp(self.typeIdx, other.typeIdx)
    pass


class _DEX_AnnotationItem(_DEX_AnnotationItem_novisibility):
    visibility = uint8
    
    child_names = 'visibility typeIdx size members'.split()
    pass


_DEX_AnnotationMember. \
    value_map[_DEX_AnnotationMember.kDexAnnotationAnnotation] = \
    _DEX_AnnotationItem_novisibility


class _DEX_EncodedArrayItem(composite):
    size = uleb128
    elements = array('size', _DEX_AnnotationMember_noname)

    child_names = 'size elements'.split()
    pass


class _DEX_DebugCodeBlock(_dex_type):
    DBG_END_SEQUENCE = 0x00
    DBG_ADVANCE_PC = 0x01
    DBG_ADVANCE_LINE = 0x02
    DBG_START_LOCAL = 0x03
    DBG_START_LOCAL_EXTENDED = 0x04
    DBG_END_LOCAL = 0x05
    DBG_RESTART_LOCAL = 0x06
    DBG_SET_PROLOGUE_END = 0x07
    DBG_SET_EPILOGUE_BEGIN = 0x08
    DBG_SET_FILE = 0x09
    DBG_FIRST_SPECIAL = 0x0a
    DBG_LINE_BASE = -4
    DBG_LINE_RANGE = 15
    
    opcodes = None
    data_size = None
    
    @staticmethod
    def parse(parent, data, off):
        moff = man_off(off)

        self = _DEX_DebugCodeBlock()
        
        #
        # Parse debug opcodes
        #
        opcodes = []
        while True:
            opcode = _to_uint(data[moff(1):moff()])

            if opcode == self.DBG_END_SEQUENCE:
                opcodes.append((opcode,))
                break
            elif opcode == self.DBG_ADVANCE_PC:
                adv, sh = _uleb128(data[moff():moff() + 5])
                moff(sh)
                opcodes.append((opcode, adv))
                pass
            elif opcode == self.DBG_ADVANCE_LINE:
                adv, sh = _leb128(data[moff():moff() + 5])
                moff(sh)
                opcodes.append((opcode, adv))
                pass
            elif opcode in (self.DBG_START_LOCAL,
                            self.DBG_START_LOCAL_EXTENDED):
                reg, sh = _uleb128(data[moff():moff() + 5])
                moff(sh)
                name, sh = _uleb128(data[moff():moff() + 5])
                moff(sh)
                descriptor, sh = _uleb128(data[moff():moff() + 5])
                moff(sh)
                if opcode == self.DBG_START_LOCAL_EXTENDED:
                    signature, sh = _uleb128(data[moff():moff() + 5])
                    moff(sh)
                    opcodes.append((opcode, reg, name, descriptor, signature))
                else:
                    opcodes.append((opcode, reg, name, descriptor))
                    pass
                pass
            elif opcode == self.DBG_END_LOCAL:
                reg, sh = _uleb128(data[moff():moff() + 5])
                moff(sh)
                opcodes.append((opcode, reg))
                pass
            elif opcode == self.DBG_RESTART_LOCAL:
                reg, sh = _uleb128(data[moff():moff() + 5])
                moff(sh)
                opcodes.append((opcode, reg))
                pass
            elif opcode in (self.DBG_SET_PROLOGUE_END,
                            self.DBG_SET_EPILOGUE_BEGIN,
                            self.DBG_SET_FILE):
                opcodes.append((opcode,))
                pass
            else:
                opcodes.append((opcode,))
                pass
            pass
        self.opcodes = tuple(opcodes)

        self.data_size = moff() - off
        
        return self

    def compute_size(self):
        import itertools
        
        def compute_opcode_size(code):
            opcode = code[0]
            
            if opcode == self.DBG_END_SEQUENCE:
                size = 1
            elif opcode == self.DBG_ADVANCE_PC:
                size = 1 + _uleb128_sz(code[1])
            elif opcode == self.DBG_ADVANCE_LINE:
                size = 1 + _leb128_sz(code[1])
            elif opcode in (self.DBG_START_LOCAL,
                            self.DBG_START_LOCAL_EXTENDED):
                size = 1 + _uleb128_sz(code[1]) + _uleb128_sz(code[2]) + \
                    _uleb128_sz(code[3])
                if len(code) == 5:
                    size = size + _uleb128_sz(code[4])
                    pass
                pass
            elif opcode == self.DBG_END_LOCAL:
                size = 1 + _uleb128_sz(code[1])
            elif opcode == self.DBG_RESTART_LOCAL:
                size = 1 + _uleb128_sz(code[1])
            elif opcode in (self.DBG_SET_PROLOGUE_END,
                            self.DBG_SET_EPILOGUE_BEGIN,
                            self.DBG_SET_FILE):
                size = 1
            else:
                size = 1
                pass
            
            return size

        opcode_sizes = itertools.imap(compute_opcode_size, self.opcodes)
        opcode_sizes = [i for i in opcode_sizes]
        opcodes_size = sum(opcode_sizes)
        
        self.data_size = opcodes_size
        pass

    @staticmethod
    def sizeof(obj):
        return obj.data_size
    
    @staticmethod
    def to_str(self):
        #
        # Parse debug opcodes
        #
        opcodes = self.opcodes
        opcodebins = []
        for code in opcodes:
            opcode = code[0]

            if opcode == self.DBG_END_SEQUENCE:
                opcodebins.append(chr(opcode))
                break
            elif opcode == self.DBG_ADVANCE_PC:
                codebin = chr(opcode) + _to_uleb128(code[1])
                opcodebins.append(codebin)
                pass
            elif opcode == self.DBG_ADVANCE_LINE:
                codebin = chr(opcode) + _to_leb128(code[1])
                opcodebins.append(codebin)
                pass
            elif opcode == self.DBG_START_LOCAL:
                codebin = chr(opcode) + _to_uleb128(code[1]) + \
                    _to_uleb128(code[2]) + _to_uleb128(code[3])
                opcodebins.append(codebin)
                pass
            elif opcode == self.DBG_START_LOCAL_EXTENDED:
                codebin = chr(opcode) + _to_uleb128(code[1]) + \
                    _to_uleb128(code[2]) + _to_uleb128(code[3]) + \
                    _to_uleb128(code[4])
                opcodebins.append(codebin)
                pass
            elif opcode == self.DBG_END_LOCAL:
                codebin = chr(opcode) + _to_uleb128(code[1])
                opcodebins.append(codebin)
                pass
            elif opcode == self.DBG_RESTART_LOCAL:
                codebin = chr(opcode) + _to_uleb128(code[1])
                opcodebins.append(codebin)
                pass
            elif opcode in (self.DBG_SET_PROLOGUE_END,
                            self.DBG_SET_EPILOGUE_BEGIN,
                            self.DBG_SET_FILE):
                opcodebins.append(chr(opcode))
                pass
            else:
                opcodebins.append(chr(opcode))
                pass
            pass

        return ''.join(opcodebins)

    def children(self):
        return ()
    pass


class _DEX_DebugInfoItem(composite):
    start_line = uleb128
    parameters_size = uleb128
    parameters = array('parameters_size', uleb128)
    opcodes = _DEX_DebugCodeBlock

    child_names = 'start_line parameters_size parameters opcodes'.split()
    pass


class _DEX_StringDataItem(composite):
    size = uleb128
    data = rawstr_size_name('size')
    padding = rawstr(1)

    child_names = 'size data padding'.split()
    pass
    

class dummy(_dex_type):
    data_size = None

    @staticmethod
    def parse(parent, data, off):
        size, sh = _uleb128(data[off:off + 5])
        data = data[off + sh: off + sh + size]

        self = _DEX_StringDataItem()

        self.size = size
        self.data = data
        self.data_size = sh + size + 1
        return self

    def compute_size(self):
        size = len(self.data)
        self.size = size
        size_sz = _uleb128_sz(size)
        self.data_size = size_sz + size + 1
        pass

    @staticmethod
    def to_str(self):
        size = len(self.data)
        self.size = size
        data = _uleb128(size) + self.data + '\x00'
        return data
    pass


class DEXFile(composite):
    fname = None
    data = None
    header = _DEX_header
    maps = _DEX_MapItemBlock
    stringIds = array_sorted(None, _DEX_StringId)
    typeIds = array_sorted(None, _DEX_TypeId)
    protoIds = array_sorted(None, _DEX_ProtoId)
    fieldIds = array_sorted(None, _DEX_FieldId)
    methodIds = array_sorted(None, _DEX_MethodId)
    classDefs = array(None, _DEX_ClassDef)
    classDatas = array(None, _DEX_ClassData)
    typeLists = array(None, _DEX_TypeList_align)
    codeItems = array(None, _DEX_Code)
    annotationSetItems = array(None, _DEX_AnnotationSetItem)
    annotationsDirectoryItems = array(None, _DEX_AnnotationsDirectoryItem)
    annotationItems = array_sorted(None, _DEX_AnnotationItem)
    encodedArrayItems = array(None, _DEX_EncodedArrayItem)
    debugInfoItems = array(None, _DEX_DebugInfoItem)
    stringDataItems = array(None, _DEX_StringDataItem)

    child_names = 'header'.split()

    block_defs = {
        0x0000: 'header',
        0x0001: 'stringIds',
        0x0002: 'typeIds',
        0x0003: 'protoIds',
        0x0004: 'fieldIds',
        0x0005: 'methodIds',
        0x0006: 'classDefs',
        0x1000: 'maps',
        0x1001: 'typeLists',
        # 0x1002: 'kDexTypeAnnotationSetRefList',
        0x1003: 'annotationSetItems',
        0x2000: 'classDatas',
        0x2001: 'codeItems',
        0x2002: 'stringDataItems',
        0x2003: 'debugInfoItems',
        0x2004: 'annotationItems',
        0x2005: 'encodedArrayItems',
        0x2006: 'annotationsDirectoryItems'
        }
    
    @staticmethod
    def open(fname):
        fo = file(fname, 'r')
        data = fo.read()

        dex = DEXFile.parse(data)
        dex.fname = fname
        return dex

    @classmethod
    def parse(clazz, data):
        obj = super(DEXFile, clazz).parse(None, data, 0)
        obj.data = data
        obj._parse(data)
        return obj

    def _parse_maps(self):
        data = self.data
        header = self.header
        off = header.mapOff
        self.parse_child('maps', data, off)
        pass

    def _parse_block(self, block_map):
        if block_map.type not in self.block_defs:
            import sys
            print >> sys.stderr, \
                'Warning: unknown map type 0x%x' % (block_map.type)
            return

        data = self.data
        
        child_name = self.block_defs[block_map.type]
        off = block_map.offset
        num = block_map.size
        
        child_clazz = getattr(self.__class__, child_name)
        blk = child_clazz.parse_nitem(self, data, off, num)
        setattr(self, child_name, blk)
        pass

    def _parse_blocks(self):
        data = self.data
        maps = self.maps.items.items
        for map in maps:
            if map.type in (0x0000, 0x1000): # header and maps
                continue
            if map.type in self.block_defs:
                self._parse_block(map)
                pass
            pass
        pass

    def _parse(self, data):
        self._parse_maps()
        self._parse_blocks()
        pass

    def children(self):
        map_items = [self.block_defs[map_item.type]
                     for map_item in self.maps.items.items]
        children = map_items
        return children

    ## \biref Make SHA1 signature for DEX.
    #
    # This method must be called before make_checksum().
    #
    def make_signature(self):
        from hashlib import sha1

        raw = self.to_str()
        sz = self.header.fileSize
        nosum = _DEX_header.magic.sizeof(self.header.magic) + \
            _DEX_header.checksum.sizeof(self.header.checksum) + \
            _DEX_header.signature.sizeof(self.header.signature)
        sha = sha1()
        sha.update(raw[nosum:])
        signature = sha.digest()
        self.header.signature.data = signature
        pass

    def make_checksum(self):
        from paraspace.tools import adler32, adler32_init_value
        
        raw = self.to_str()
        sz = self.header.fileSize
        nosum = _DEX_header.magic.sizeof(self.header.magic) + \
            _DEX_header.checksum.sizeof(self.header.checksum)
        checksum = adler32(adler32_init_value, raw, nosum, sz - nosum)
        self.header.checksum = checksum
        pass
    pass


## \brief A linked version of a DEXFile.
#
# Instances of this class was built from instances of DEXFile.
# Dependencies are linked to depend-on objects; the target of a
# dependence.
#
class DEXFile_linked(DEXFile):
    _dep_decls = None
    
    def _copy_attributes(self, dex):
        for attr, value in dex.__dict__.items():
            setattr(self, attr, value)
            pass
        pass

    ## \brief Factory function to return a DEXFile_linked of given DEXFile.
    #
    # \param dex is a DEXFile instance.
    # \param dep_decls is a dictionary returned by prepare_dep_decls().
    # \return a DEXFile_linked.
    #
    @staticmethod
    def build_dependencies(dex, dep_decls):
        from paraspace.dex_deptracker import build_dependencies

        if not isinstance(dex, DEXFile):
            raise TypeError, 'first argument must be an instance of DEXFile'
        
        linked = DEXFile_linked()
        build_dependencies(dex, dep_decls)
        linked._copy_attributes(dex)

        linked._dep_decls = dep_decls
        
        return linked
    
    ## \brief Return name string of a linked class definition item
    @staticmethod
    def get_classdef_name(classdef):
        return DEXFile_linked.get_typeid_name(classdef.classIdx)

    ## \brief Return name string of a linked type ID item.
    @staticmethod
    def get_typeid_name(typeid):
        return typeid.descriptorIdx.stringDataOff.data.data

    ## \brief Get index of given type ID.
    def get_idx_typeid(self, typeid):
        return self.typeIds.items.index(typeid)

    ## \brief Find type ID item with given name.
    def find_typeid_name(self, name):
        for typeid in self.typeIds.items:
            typeid_name = DEXFile_linked.get_typeid_name(typeid)
            if typeid_name == name:
                return typeid
            pass
        pass

    ## \brief Get index of given _DEX_ClassDef.
    def get_idx_classdef(self, classdef):
        from paraspace.dexfile import _DEX_ClassDef
        assert isinstance(classdef, _DEX_ClassDef)
        typeidx = self.get_idx_typeid(classdef.classIdx)
        return typeidx
    
    ## \brief Return type ID item with given index.
    def find_typeid_idx(self, idx):
        return self.typeIds.items[idx]
    
    def find_class_name(self, name):
        for classdef in self.classDefs.items:
            classdef_name = DEXFile_linked.get_classdef_name(classdef)
            if classdef_name == name:
                return classdef
            pass
        raise ValueError, 'can not find class definition for \'%s\'' % (name)

    ## \brief Return a class definition corresponding for give type ID.
    def find_class_typeid(self, typeid):
        for classdef in self.classDefs.items:
            if classdef.classIdx == typeid:
                return classdef
            pass
        raise ValueError, \
            'can not find class definition for typeid %s' % (repr(typeid))

    ## \brief Update size of map items.
    #
    # Corresponding data lists of maps may be changed, it should be updated
    # before restore dependencies and keep it consistent.
    #
    def _update_map_sizes(self):
        for mapitem in self.maps.items.items:
            attr = DEXFile.block_defs[mapitem.type]
            datalist = getattr(self, attr)
            if isinstance(datalist, array):
                mapitem.size = len(datalist.items)
                pass
            pass
        pass

    ## \brief Return an unlinked version.
    def get_unlinked(self):
        from paraspace.dex_deptracker import restore_dependencies

        self._update_map_sizes()
        
        unlinked = DEXFile()
        for attr, value in self.__dict__.items():
            setattr(unlinked, attr, value)
            pass

        restore_dependencies(unlinked, self._dep_decls)
        
        return unlinked

    ## \brief Insert a linked class definition into the DEX file.
    def insert_class(self, classdef):
        from paraspace.injection import dexfile_insert_class
        
        assert isinstance(classdef, _DEX_ClassDef)

        clone = dexfile_insert_class(self, classdef)
        return clone

    ## \brief Get name string of given method.
    @staticmethod
    def get_method_name(method):
        methodid = method.methodIdx
        return DEXFile_linked.get_methodid_name(methodid)

    ## \brief Get name string of given method ID.
    @staticmethod
    def get_methodid_name(methodid):
        namestrid = methodid.nameIdx
        namestrdata = namestrid.stringDataOff
        name_str = namestrdata.data.data
        return name_str

    ## \brief Find the method of given method name and class definition.
    #
    # \param method_name is the method name.
    # \param classdef is a _DEX_ClassDef.
    # \return the corresponding _DEX_Method of given method_name and classdef.
    #
    def find_method_name(self, method_name, classdef):
        if not classdef.classDataOffRef.is_true:
            return

        classdata = classdef.classDataOffRef.value
        for wmethod in classdata.directMethods.items + \
                classdata.virtualMethods.items:
            wmethod_name = DEXFile_linked.get_method_name(wmethod)
            if method_name == wmethod_name:
                return wmethod
            pass
        pass

    ## \brief Return index of given method.
    def get_idx_method(self, method):
        methodid = method.methodIdx
        idx = self.methodIds.items.index(methodid)
        return idx

    ## \brief Find the method ID item of given index.
    def find_methodid_idx(self, idx):
        methodid = self.methodIds.items[idx]
        return methodid

    ## \brief Find a method definition with an index to method ID.
    def find_method_idx(self, idx):
        methodid = self.find_methodid_idx(idx)
        method_name = DEXFile_linked.get_methodid_name(methodid)
        method_proto = methodid.protoIdx
        method_typeid = methodid.classIdx
        classdef = self.find_class_typeid(method_typeid)
        
        method = self.find_method_name_proto(method, method_proto, classdef)
        
        return method

    ## \brief Test if prototype of two methods are compatible.
    @staticmethod
    def _proto_is_compatible(proto1, proto2):
        rtypename1 = DEXFile_linked.get_typeid_name(proto1.returnTypeIdx)
        rtypename2 = DEXFile_linked.get_typeid_name(proto2.returnTypeIdx)
        if rtypename1 != rtypename2:
            return False
        typelist1 = proto1.parametersOffRef.value
        typelist2 = proto2.parametersOffRef.value
        if len(typelist1.typeItems.items) != len(typelist2.typeItems.items):
            return False

        for tl_typeid1, tl_typeid2 in map(None,
                                          typelist1.typeItems.items,
                                          typelist2.typeItems.items):
            typename1 = DEXFile_linked.get_typeid_name(tl_typeid1.typeIdx)
            typename2 = DEXFile_linked.get_typeid_name(tl_typeid2.typeIdx)
            
            if typename1 != typename2:
                return False
            pass
        return True

    ## \brief Find the method of given name, prototype and class definition.
    def find_method_name_proto(self, method_name, proto, classdef):
        if not classdef.classDataOffRef.is_true:
            return

        classdata = classdef.classDataOffRef.value
        for wmethod in classdata.directMethods.items + \
                classdata.virtualMethods.items:
            wmethod_name = DEXFile_linked.get_method_name(wmethod)
            if method_name != wmethod_name:
                continue
            wmethodid = wmethod.methodIdx
            if DEXFile_linked._proto_is_compatible(wmethodid.protoIdx, proto):
                return wmethod
            pass
        raise ValueError, 'can not find a method for given name and prototype'

    ## \brief Return index of given method ID.
    def get_idx_methodid(self, methodid):
        idx = self.methodIds.items.index(methodid)
        return idx
    
    ## \brief Return method ID for given name, proto, and typeid/
    def find_methodid_name_proto(self, method_name, proto, typeid):
        for methodid in self.methodIds.items:
            if method_name != DEXFile_linked.get_methodid_name(methodid):
                continue
            if methodid.classIdx != typeid:
                continue
            if not DEXFile_linked. \
                    _proto_is_compatible(methodid.protoIdx, proto):
                continue
            return methodid
        raise ValueError, 'can not find the method ID for given name, ' \
            'prototype and type ID'

    @staticmethod
    def get_param_typeids_protoid(protoid):
        if not protoid.parametersOffRef.is_true:
            return ()
        tl_typeids = protoid.parametersOffRef.value.typeItems.items
        typeids = [tl_typeid.typeIdx
                   for tl_typeid in tl_typeids]
        return typeids

    ## \brief Return code block of given method.
    #
    # Code block is a string of byte code instructions for Dalvik VM.
    #
    @staticmethod
    def get_code_block_method(method):
        if not method.codeOffRef.is_true:
            return ''

        code = method.codeOffRef.value
        insns = code.insns.data
        return insns

    ## \brief Return all method of given class definition.
    @staticmethod
    def get_methods_classdef(classdef):
        if not classdef.classDataOffRef.is_true:
            return []
        classdata = classdef.classDataOffRef.value
        methods = classdata.directMethods.items + \
            classdata.virtualMethods.items
        return methods

    ## \brief Find all method IDs that is part of given type.
    #
    # \param typeid is ID of type that IDs of its methods will be returned.
    # \return a list of method IDs.
    #
    def find_methodids_typeid(self, typeid):
        methodids = [methodid
                     for methodid in self.methodIds.items
                     if methodid.classIdx == typeid]
        return methodids

    ## \brief Dump content of a proto ID.
    @staticmethod
    def dump_protoid(protoid):
        rtype_name = DEXFile_linked.get_typeid_name(protoid.returnTypeIdx)
        param_types = DEXFile_linked.get_param_typeids_protoid(protoid)
        ptype_names = [DEXFile_linked.get_typeid_name(ptype)
                       for ptype in param_types]
        return '(%s) --> %s' % (', '.join(ptype_names), rtype_name)

    @staticmethod
    def make_protoid(rtype, args):
        arglist = _DEX_TypeList()
        arglist.num = len(args)
        arglist.typeItems = array(None, _DEX_TypeList_typeid)
        
        tltypeid_args = [_DEX_TypeList_typeid()
                         for arg in args]
        for tltypeid, arg in map(None, tltypeid_args, args):
            tltypeid.typeIdx = arg
            pass
        
        arglist.typeItems.items = tltypeid_args

        param_cond = cond(None, _DEX_TypeList)
        param_cond.value = arglist
        param_cond.is_true = True
        
        protoid = _DEX_ProtoId()
        protoid.returnTypeIdx = rtype
        protoid.parametersOffRef = param_cond
        return protoid
    pass


if __name__ == '__main__':
    import sys
    
    if len(sys.argv) != 2:
        print >> sys.stderr, 'Usage: %s <dex file>' % (sys.argv[0])
        sys.exit(1)
        pass
    
    dex_fname = sys.argv[1]
    dex = DEXFile.open(dex_fname)
    
    print 'Header'
    h = dex.header
    for attr in h.child_names:
        print '\t%s: %s' % (attr, repr(getattr(h, attr)))
        pass

    print
    print 'Size of stringIds is %d bytes' % (dex.stringIds.data_size)

    print
    print 'Size of typeIds is %d bytes' % (dex.typeIds.data_size)

    print
    print 'Size of protoIds is %d bytes' % (dex.protoIds.data_size)

    print
    print 'Size of fieldIds is %d bytes' % (dex.fieldIds.data_size)

    print
    print 'Size of methodIds is %d bytes' % (dex.methodIds.data_size)

    print
    print 'Size of classDefs is %d bytes' % (dex.classDefs.data_size)

    print
    print 'Size of classDatas is %d bytes' % (dex.classDatas.data_size)

    print
    print 'Size of typeLists is %d bytes' % (dex.typeLists.data_size)

    print
    print 'Size of codeItems is %d bytes' % (dex.codeItems.data_size)

    print
    print 'Size of annotationSetItems is %d bytes' % \
        (dex.annotationSetItems.data_size)

    print
    print 'Size of annotationsDirectoryItems is %d bytes' % \
        (dex.annotationsDirectoryItems.data_size)

    print
    print 'Size of annotationItems is %d bytes' % \
        (dex.annotationItems.data_size)

    print
    print 'Size of encodedArrayItems is %d bytes' % \
        (dex.encodedArrayItems.data_size)

    print
    print 'Size of debugInfoItems is %d bytes' % \
        (dex.debugInfoItems.data_size)

    print
    print 'Size of stringDataItems is %d bytes' % \
        (dex.stringDataItems.data_size)

    print
    print 'Data maps'
    maps = dex.maps.items.items
    for map in maps:
        print '\t0x%04x(%s) size=%d offset=0x%08x' % (map.type,
                                                      map.types[map.type],
                                                      map.size,
                                                      map.offset)
        pass
    pass