text: # -*- coding: utf-8 -*-
  """
  Device Tree Blob Parser
  
     Copyright 2014  Neil 'superna' Armstrong <superna9999@gmail.com>
  
     Licensed under the Apache License, Version 2.0 (the "License");
     you may not use this file except in compliance with the License.
     You may obtain a copy of the License at
  
       http://www.apache.org/licenses/LICENSE-2.0
  
     Unless required by applicable law or agreed to in writing, software
     distributed under the License is distributed on an "AS IS" BASIS,
     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     See the License for the specific language governing permissions and
     limitations under the License.
  
  @author: Neil 'superna' Armstrong <superna9999@gmail.com>
  """
  
  import string
  import os
  import json
  from copy import deepcopy, copy
  from struct import Struct, unpack, pack
  
  FDT_MAGIC = 0xd00dfeed
  FDT_BEGIN_NODE = 0x1
  FDT_END_NODE = 0x2
  FDT_PROP = 0x3
  FDT_NOP = 0x4
  FDT_END = 0x9
  
  INDENT = ' ' * 4
  
  FDT_MAX_VERSION = 17
  
  
  class FdtProperty(object):
      """ Represents an empty property"""
  
      @staticmethod
      def __validate_dt_name(name):
          """Checks the name validity"""
          return not any([True for char in name
                          if char not in string.printable])
  
      def __init__(self, name):
          """Init with name"""
          self.name = name
          if not FdtProperty.__validate_dt_name(self.name):
              raise Exception("Invalid name '%s'" % self.name)
  
      def get_name(self):
          """Get property name"""
          return self.name
  
      def __str__(self):
          """String representation"""
          return "Property(%s)" % self.name
  
      def dts_represent(self, depth=0):
          """Get dts string representation"""
          return INDENT*depth + self.name + ';'
  
      def dtb_represent(self, string_store, pos=0, version=17):
          """Get blob representation"""
          # print "%x:%s" % (pos, self)
          strpos = string_store.find(self.name+'\0')
          if strpos < 0:
              strpos = len(string_store)
              string_store += self.name+'\0'
          pos += 12
          return (pack('>III', FDT_PROP, 0, strpos),
                  string_store, pos)
  
      def json_represent(self, depth=0):
          """Ouput JSON"""
          return '%s: null' % json.dumps(self.name)
  
      def to_raw(self):
          """Return RAW value representation"""
          return ''
  
      def __getitem__(self, value):
          """Returns No Items"""
          return None
  
      def __ne__(self, node):
          """Check property inequality
          """
          return not self.__eq__(node)
  
      def __eq__(self, node):
          """Check node equality
             check properties are the same (same values)
          """
          if not isinstance(node, FdtProperty):
              raise Exception("Invalid object type")
          if self.name != node.get_name():
              return False
          return True
  
      @staticmethod
      def __check_prop_strings(value):
          """Check property string validity
             Python version of util_is_printable_string from dtc
          """
          pos = 0
          posi = 0
          end = len(value)
          
          if not len(value):
              return None   
          
          #Needed for python 3 support: If a bytes object is passed,
          #decode it with the ascii codec. If the decoding fails, assume
          #it was not a string object.
          try:
              value = value.decode('ascii')
          except ValueError:
              return None
          
          #Test both against string 0 and int 0 because of python2/3 compatibility
          if value[-1] != '\0':
              return None
  
          while pos < end:
              posi = pos
              while pos < end and value[pos] != '\0' \
                    and value[pos] in string.printable \
                    and value[pos] not in ('\r', '\n'):
                  pos += 1
  
              if value[pos] != '\0' or pos == posi:
                  return None
              pos += 1
  
          return True
  
      @staticmethod
      def new_raw_property(name, raw_value):
          """Instantiate property with raw value type"""
          if FdtProperty.__check_prop_strings(raw_value):
              return FdtPropertyStrings.init_raw(name, raw_value)
          elif len(raw_value) and len(raw_value) % 4 == 0:
              return FdtPropertyWords.init_raw(name, raw_value)
          elif len(raw_value):
              return FdtPropertyBytes.init_raw(name, raw_value)
          else:
              return FdtProperty(name)
  
  
  class FdtPropertyStrings(FdtProperty):
      """Property with strings as value"""
  
      @classmethod
      def __extract_prop_strings(cls, value):
          """Extract strings from raw_value"""
          return [st for st in \
              value.decode('ascii').split('\0') if len(st)]
  
      def __init__(self, name, strings):
          """Init with strings"""
          FdtProperty.__init__(self, name)
          if not strings:
              raise Exception("Invalid strings")
          for stri in strings:
              if len(stri) == 0:
                  raise Exception("Invalid strings")
              if any([True for char in stri
                          if char not in string.printable 
                             or char in ('\r', '\n')]):
                  raise Exception("Invalid chars in strings")
          self.strings = strings
  
      @classmethod
      def init_raw(cls, name, raw_value):
          """Init from raw"""
          return cls(name, cls.__extract_prop_strings(raw_value))
  
      def dts_represent(self, depth=0):
          """Get dts string representation"""
          return INDENT*depth + self.name + ' = "' + \
              '", "'.join(self.strings) + '";'
  
      def dtb_represent(self, string_store, pos=0, version=17):
          """Get blob representation"""
          # print "%x:%s" % (pos, self)
          blob = pack('')
          for chars in self.strings:
              blob += chars.encode('ascii') + pack('b', 0)
          blob_len = len(blob)
          if version < 16 and (pos+12) % 8 != 0:
              blob = pack('b', 0) * (8-((pos+12) % 8)) + blob
          if blob_len % 4:
              blob += pack('b', 0) * (4-(blob_len % 4))
          strpos = string_store.find(self.name+'\0')
          if strpos < 0:
              strpos = len(string_store)
              string_store += self.name+'\0'
          blob = pack('>III', FDT_PROP, blob_len, strpos) + blob
          pos += len(blob)
          return (blob, string_store, pos)
  
      def json_represent(self, depth=0):
          """Ouput JSON"""
          result = '%s: ["strings", ' % json.dumps(self.name)
          result += ', '.join([json.dumps(stri) for stri in self.strings])
          result += ']'
          return result
  
      def to_raw(self):
          """Return RAW value representation"""
          return ''.join([chars+'\0' for chars in self.strings])
  
      def __str__(self):
          """String representation"""
          return "Property(%s,Strings:%s)" % (self.name, self.strings)
  
      def __getitem__(self, index):
          """Get strings, returns a string"""
          return self.strings[index]
  
      def __len__(self):
          """Get strings count"""
          return len(self.strings)
  
      def __eq__(self, node):
          """Check node equality
             check properties are the same (same values)
          """
          if not FdtProperty.__eq__(self, node):
              return False
          if self.__len__() != len(node):
              return False
          for index in range(self.__len__()):
              if self.strings[index] != node[index]:
                  return False
          return True
  
  class FdtPropertyWords(FdtProperty):
      """Property with words as value"""
  
      def __init__(self, name, words):
          """Init with words"""
          FdtProperty.__init__(self, name)
          for word in words:
              if not 0 <= word <= 4294967295:
                  raise Exception("Invalid word value %d, requires 0 <= number <= 4294967295" % word)
          if not len(words):
              raise Exception("Invalid Words")
          self.words = words
  
      @classmethod
      def init_raw(cls, name, raw_value):
          """Init from raw"""
          if len(raw_value) % 4 == 0:
              words = [unpack(">I", raw_value[i:i+4])[0]
                       for i in range(0, len(raw_value), 4)]
              return cls(name, words)
          else:
              raise Exception("Invalid raw Words")
  
      def dts_represent(self, depth=0):
          """Get dts string representation"""
          return INDENT*depth + self.name + ' = <' + \
                 ' '.join(["0x%08x" % word for word in self.words]) + ">;"
  
      def dtb_represent(self, string_store, pos=0, version=17):
          """Get blob representation"""
          # # print "%x:%s" % (pos, self)
          strpos = string_store.find(self.name+'\0')
          if strpos < 0:
              strpos = len(string_store)
              string_store += self.name+'\0'
          blob = pack('>III', FDT_PROP, len(self.words)*4, strpos) + \
                  pack('').join([pack('>I', word) for word in self.words])
          pos += len(blob)
          return (blob, string_store, pos)
  
      def json_represent(self, depth=0):
          """Ouput JSON"""
          result = '%s: ["words", "' % json.dumps(self.name)
          result += '", "'.join(["0x%08x" % word for word in self.words])
          result += '"]'
          return result
  
      def to_raw(self):
          """Return RAW value representation"""
          return ''.join([pack('>I', word) for word in self.words])
  
      def __str__(self):
          """String representation"""
          return "Property(%s,Words:%s)" % (self.name, self.words)
  
      def __getitem__(self, index):
          """Get words, returns a word integer"""
          return self.words[index]
  
      def __len__(self):
          """Get words count"""
          return len(self.words)
  
      def __eq__(self, node):
          """Check node equality
             check properties are the same (same values)
          """
          if not FdtProperty.__eq__(self, node):
              return False
          if self.__len__() != len(node):
              return False
          for index in range(self.__len__()):
              if self.words[index] != node[index]:
                  return False
          return True
  
  
  class FdtPropertyBytes(FdtProperty):
      """Property with signed bytes as value"""
  
      def __init__(self, name, bytez):
          """Init with bytes"""
          FdtProperty.__init__(self, name)
          for byte in bytez:
              if not -128 <= byte <= 127:
                  raise Exception("Invalid value for byte %d, requires -128 <= number <= 127" % byte)
          if not bytez:
              raise Exception("Invalid Bytes")
          self.bytes = bytez
  
      @classmethod
      def init_raw(cls, name, raw_value):
          """Init from raw"""
          return cls(name, unpack('b' * len(raw_value), raw_value))
  
      def dts_represent(self, depth=0):
          """Get dts string representation"""
          return INDENT*depth + self.name + ' = [' + \
              ' '.join(["%02x" % (byte & int('ff',16)) 
                        for byte in self.bytes]) + "];"
  
      def dtb_represent(self, string_store, pos=0, version=17):
          """Get blob representation"""
          # print "%x:%s" % (pos, self)
          strpos = string_store.find(self.name+'\0')
          if strpos < 0:
              strpos = len(string_store)
              string_store += self.name+'\0'
          blob = pack('>III', FDT_PROP, len(self.bytes), strpos)
          blob += pack('').join([pack('>b', byte) for byte in self.bytes])
          if len(blob) % 4:
              blob += pack('b', 0) * (4-(len(blob) % 4))
          pos += len(blob)
          return (blob, string_store, pos)
  
      def json_represent(self, depth=0):
          """Ouput JSON"""
          result = '%s: ["bytes", "' % json.dumps(self.name)
          result += '", "'.join(["%02x" % byte
                                  for byte in self.bytes])
          result += '"]'
          return result
  
      def to_raw(self):
          """Return RAW value representation"""
          return ''.join([pack('>b', byte) for byte in self.bytes])
  
      def __str__(self):
          """String representation"""
          return "Property(%s,Bytes:%s)" % (self.name, self.bytes)
  
      def __getitem__(self, index):
          """Get bytes, returns a byte"""
          return self.bytes[index]
  
      def __len__(self):
          """Get strings count"""
          return len(self.bytes)
  
      def __eq__(self, node):
          """Check node equality
             check properties are the same (same values)
          """
          if not FdtProperty.__eq__(self, node):
              return False
          if self.__len__() != len(node):
              return False
          for index in range(self.__len__()):
              if self.bytes[index] != node[index]:
                  return False
          return True
  
  
  class FdtNop(object):  # pylint: disable-msg=R0903
      """Nop child representation"""
  
      def __init__(self):
          """Init with nothing"""
  
      def get_name(self):  # pylint: disable-msg=R0201
          """Return name"""
          return None
  
      def __str__(self):
          """String representation"""
          return ''
  
      def dts_represent(self, depth=0):  # pylint: disable-msg=R0201
          """Get dts string representation"""
          return INDENT*depth+'// [NOP]'
  
      def dtb_represent(self, string_store, pos=0, version=17):
          """Get blob representation"""
          # print "%x:%s" % (pos, self)
          pos += 4
          return (pack('>I', FDT_NOP), string_store, pos)
  
  
  class FdtNode(object):
      """Node representation"""
  
      @staticmethod
      def __validate_dt_name(name):
          """Checks the name validity"""
          return not any([True for char in name
                          if char not in string.printable])
  
      def __init__(self, name):
          """Init node with name"""
          self.name = name
          self.subdata = []
          self.parent = None
          if not FdtNode.__validate_dt_name(self.name):
              raise Exception("Invalid name '%s'" % self.name)
  
      def get_name(self):
          """Get property name"""
          return self.name
  
      def __check_name_duplicate(self, name):
          """Checks if name is not in a subnode"""
          for data in self.subdata:
              if not isinstance(data, FdtNop) \
                 and data.get_name() == name:
                     return True
          return False
  
      def add_subnode(self, node):
          """Add child, deprecated use append()"""
          self.append(node)
  
      def add_raw_attribute(self, name, raw_value):
          """Construct a raw attribute and add to child"""
          self.append(FdtProperty.new_raw_property(name, raw_value))
  
      def set_parent_node(self, node):
          """Set parent node, None and FdtNode accepted"""
          if node is not None and \
             not isinstance(node, FdtNode):
              raise Exception("Invalid object type")
          self.parent = node
  
      def get_parent_node(self):
          """Get parent node"""
          return self.parent
  
      def __str__(self):
          """String representation"""
          return "Node(%s)" % self.name
  
      def dts_represent(self, depth=0):
          """Get dts string representation"""
          result = ('\n').join([sub.dts_represent(depth+1)
                                           for sub in self.subdata])
          if len(result) > 0:
              result += '\n'
          return INDENT*depth + self.name + ' {\n' + \
                 result + INDENT*depth + "};"
  
      def dtb_represent(self, strings_store, pos=0, version=17):
          """Get blob representation
             Pass string storage as strings_store, pos for current node start
             and version as current dtb version
          """
          # print "%x:%s" % (pos, self)
          strings = strings_store
          if self.get_name() == '/':
              blob = pack('>II', FDT_BEGIN_NODE, 0)
          else:
              blob = pack('>I', FDT_BEGIN_NODE)
              blob += self.get_name().encode('ascii') + pack('b', 0)
          if len(blob) % 4:
              blob += pack('b', 0) * (4-(len(blob) % 4))
          pos += len(blob)
          for sub in self.subdata:
              (data, strings, pos) = sub.dtb_represent(strings, pos, version)
              blob += data
          pos += 4
          blob += pack('>I', FDT_END_NODE)
          return (blob, strings, pos)
  
      def json_represent(self, depth=0):
          """Get dts string representation"""
          result = (',\n'+ \
                    INDENT*(depth+1)).join([sub.json_represent(depth+1)
                                            for sub in self.subdata
                                            if not isinstance(sub, FdtNop)])
          if len(result) > 0:
              result = INDENT + result + '\n'+INDENT*depth
          if self.get_name() == '/':
              return "{\n" + INDENT*(depth) + result + "}"
          else:
              return json.dumps(self.name) + ': {\n' + \
                     INDENT*(depth) + result + "}"
  
      def __getitem__(self, index):
          """Get subnodes, returns either a Node, a Property or a Nop"""
          return self.subdata[index]
  
      def __setitem__(self, index, subnode):
          """Set node at index, replacing previous subnode, 
             must not be a duplicate name
          """
          if self.subdata[index].get_name() != subnode.get_name() and \
             self.__check_name_duplicate(subnode.get_name()):
              raise Exception("%s : %s subnode already exists" % \
                                          (self, subnode))
          if not isinstance(subnode, (FdtNode, FdtProperty, FdtNop)):
              raise Exception("Invalid object type")
          self.subdata[index] = subnode
  
      def __len__(self):
          """Get strings count"""
          return len(self.subdata)
  
      def __ne__(self, node):
          """Check node inequality
             i.e. is subnodes are the same, in either order
             and properties are the same (same values)
             The FdtNop is excluded from the check
          """
          return not self.__eq__(node)
  
      def __eq__(self, node):
          """Check node equality
             i.e. is subnodes are the same, in either order
             and properties are the same (same values)
             The FdtNop is excluded from the check
          """
          if not isinstance(node, FdtNode):
              raise Exception("Invalid object type")
          if self.name != node.get_name():
              return False
          curnames = set([subnode.get_name() for subnode in self.subdata
                                      if not isinstance(subnode, FdtNop)])
          cmpnames = set([subnode.get_name() for subnode in node
                                      if not isinstance(subnode, FdtNop)])
          if curnames != cmpnames:
              return False
          for subnode in [subnode for subnode in self.subdata
                                      if not isinstance(subnode, FdtNop)]:
              index = node.index(subnode.get_name())
              if subnode != node[index]:
                  return False
          return True
  
      def append(self, subnode):
          """Append subnode, same as add_subnode"""
          if self.__check_name_duplicate(subnode.get_name()):
              raise Exception("%s : %s subnode already exists" % \
                                      (self, subnode))
          if not isinstance(subnode, (FdtNode, FdtProperty, FdtNop)):
              raise Exception("Invalid object type")
          self.subdata.append(subnode)
  
      def pop(self, index=-1):
          """Remove and returns subnode at index, default the last"""
          return self.subdata.pop(index)
  
      def insert(self, index, subnode):
          """Insert subnode before index, must not be a duplicate name"""
          if self.__check_name_duplicate(subnode.get_name()):
              raise Exception("%s : %s subnode already exists" % \
                                  (self, subnode))
          if not isinstance(subnode, (FdtNode, FdtProperty, FdtNop)):
              raise Exception("Invalid object type")
          self.subdata.insert(index, subnode)
  
      def _find(self, name):
          """Find name in subnodes"""
          for i in range(0, len(self.subdata)):
              if not isinstance(self.subdata[i], FdtNop) and \
                 name == self.subdata[i].get_name():
                  return i
          return None
  
      def remove(self, name):
          """Remove subnode with the name
             Raises ValueError is not present
          """
          index = self._find(name)
          if index is None:
              raise ValueError("Not present")
          return self.subdata.pop(index)
  
      def index(self, name):
          """Returns position of subnode with the name
             Raises ValueError is not present
          """
          index = self._find(name)
          if index is None:
              raise ValueError("Not present")
          return index
  
      def merge(self, node):
          """Merge two nodes and subnodes
             Replace current properties with the given properties
          """
          if not isinstance(node, FdtNode):
              raise Exception("Can only merge with a FdtNode")
          for subnode in [obj for obj in node 
                          if isinstance(obj, (FdtNode, FdtProperty))]:
              index = self._find(subnode.get_name())
              if index is None:
                  dup = deepcopy(subnode)
                  if isinstance(subnode, FdtNode):
                      dup.set_parent_node(self)
                  self.append(dup)
              elif isinstance(subnode, FdtNode):
                  self.subdata[index].merge(subnode)
              else:
                  self.subdata[index] = copy(subnode)
  
      def walk(self):
          """Walk into subnodes and yield paths and objects
             Returns set with (path string, node object)
          """
          node = self
          start = 0
          hist = []
          curpath = []
  
          while True:
              for index in range(start, len(node)):
                  if isinstance(node[index], (FdtNode, FdtProperty)):
                      yield ('/' + '/'.join(curpath+[node[index].get_name()]), 
                              node[index])
                  if isinstance(node[index], FdtNode):
                      if len(node[index]):
                          hist.append((node, index+1))
                          curpath.append(node[index].get_name())
                          node = node[index]
                          start = 0
                          index = -1
                          break
              if index >= 0:
                  if len(hist):
                      (node, start) = hist.pop()
                      curpath.pop()
                  else:
                      break
  
  
  class Fdt(object):
      """Flattened Device Tree representation"""
  
      def __init__(self, version=17, last_comp_version=16, boot_cpuid_phys=0):
          """Init FDT object with version and boot values"""
          self.header = {'magic': FDT_MAGIC,
                         'totalsize': 0,
                         'off_dt_struct': 0,
                         'off_dt_strings': 0,
                         'off_mem_rsvmap': 0,
                         'version': version,
                         'last_comp_version': last_comp_version,
                         'boot_cpuid_phys': boot_cpuid_phys,
                         'size_dt_strings': 0,
                         'size_dt_struct': 0}
          self.rootnode = None
          self.prenops = None
          self.postnops = None
          self.reserve_entries = None
  
      def add_rootnode(self, rootnode, prenops=None, postnops=None):
          """Add root node"""
          self.rootnode = rootnode
          self.prenops = prenops
          self.postnops = postnops
  
      def get_rootnode(self):
          """Get root node"""
          return self.rootnode
  
      def add_reserve_entries(self, reserve_entries):
          """Add reserved entries as list of dict with
             'address' and 'size' keys"""
          self.reserve_entries = reserve_entries
  
      def to_dts(self):
          """Export to DTS representation in string format"""
          result = "/dts-v1/;\n"
          result += "// version:\t\t%d\n" % self.header['version']
          result += "// last_comp_version:\t%d\n" % \
                    self.header['last_comp_version']
          if self.header['version'] >= 2:
              result += "// boot_cpuid_phys:\t0x%x\n" % \
                  self.header['boot_cpuid_phys']
          result += '\n'
          if self.reserve_entries is not None:
              for entry in self.reserve_entries:
                  result += "/memreserve/ "
                  if entry['address']:
                      result += "%#x " % entry['address']
                  else:
                      result += "0 "
                  if entry['size']:
                      result += "%#x" % entry['size']
                  else:
                      result += "0"
                  result += ";\n"
          if self.prenops:
              result += '\n'.join([nop.dts_represent() for nop in self.prenops])
              result += '\n'
          if self.rootnode is not None:
              result += self.rootnode.dts_represent()
          if self.postnops:
              result += '\n'
              result += '\n'.join([nop.dts_represent() for nop in self.postnops])
          return result
  
      def to_dtb(self):
          """Export to Blob format"""
          if self.rootnode is None:
              return None
          blob_reserve_entries = pack('')
          if self.reserve_entries is not None:
              for entry in self.reserve_entries:
                  blob_reserve_entries += pack('>QQ',
                                               entry['address'],
                                               entry['size'])
          blob_reserve_entries += pack('>QQ', 0, 0)
          header_size = 7 * 4
          if self.header['version'] >= 2:
              header_size += 4
          if self.header['version'] >= 3:
              header_size += 4
          if self.header['version'] >= 17:
              header_size += 4
          header_adjust = pack('')
          if header_size % 8 != 0:
              header_adjust = pack('b', 0) * (8 - (header_size % 8))
              header_size += len(header_adjust)
          dt_start = header_size + len(blob_reserve_entries)
          # print "dt_start %d" % dt_start
          (blob_dt, blob_strings, dt_pos) = \
              self.rootnode.dtb_represent('', dt_start, self.header['version'])
          if self.prenops is not None:
              blob_dt = pack('').join([nop.dtb_represent('')[0] 
                                 for nop in self.prenops])\
                        + blob_dt
          if self.postnops is not None:
              blob_dt += pack('').join([nop.dtb_represent('')[0] 
                                  for nop in self.postnops])
          blob_dt += pack('>I', FDT_END)
          self.header['size_dt_strings'] = len(blob_strings)
          self.header['size_dt_struct'] = len(blob_dt)
          self.header['off_mem_rsvmap'] = header_size
          self.header['off_dt_struct'] = dt_start
          self.header['off_dt_strings'] = dt_start + len(blob_dt)
          self.header['totalsize'] = dt_start + len(blob_dt) + len(blob_strings)
          blob_header = pack('>IIIIIII', self.header['magic'],
                             self.header['totalsize'],
                             self.header['off_dt_struct'],
                             self.header['off_dt_strings'],
                             self.header['off_mem_rsvmap'],
                             self.header['version'],
                             self.header['last_comp_version'])
          if self.header['version'] >= 2:
              blob_header += pack('>I', self.header['boot_cpuid_phys'])
          if self.header['version'] >= 3:
              blob_header += pack('>I', self.header['size_dt_strings'])
          if self.header['version'] >= 17:
              blob_header += pack('>I', self.header['size_dt_struct'])
          return blob_header + header_adjust + blob_reserve_entries + \
              blob_dt + blob_strings.encode('ascii')
  
      def to_json(self):
          """Ouput JSON"""
          if self.rootnode is None:
              return None
          return self.rootnode.json_represent()
  
      def resolve_path(self, path):
          """Resolve path like /memory/reg and return either a FdtNode,
              a FdtProperty or None"""
          if self.rootnode is None:
              return None
          if not path.startswith('/'):
              return None
          if len(path) > 1 and path.endswith('/'):
              path = path[:-1]
          if path == '/':
              return self.rootnode
          curnode = self.rootnode
          for subpath in path[1:].split('/'):
              found = None
              if not isinstance(curnode, FdtNode):
                  return None
              for node in curnode:
                  if subpath == node.get_name():
                      found = node
                      break
              if found is None:
                  return None
              curnode = found
          return curnode
  
  def _add_json_to_fdtnode(node, subjson):
      """Populate FdtNode with JSON dict items"""
      for (key, value) in subjson.items():
          if isinstance(value, dict):
              subnode = FdtNode(key)
              subnode.set_parent_node(node)
              node.append(subnode)
              _add_json_to_fdtnode(subnode, value)
          elif isinstance(value, list):
              if len(value) < 2:
                  raise Exception("Invalid list for %s" % key)
              if value[0] == "words":
                  words = [int(word, 16) for word in value[1:]]
                  node.append(FdtPropertyWords(key, words))
              elif value[0] == "bytes":
                  bytez = [int(byte, 16) for byte in value[1:]]
                  node.append(FdtPropertyBytes(key, bytez))
              elif value[0] == "strings":
                  node.append(FdtPropertyStrings(key, \
                              [s for s in value[1:]]))
              else:
                  raise Exception("Invalid list for %s" % key)
          elif value is None:
              node.append(FdtProperty(key))
          else:
              raise Exception("Invalid value for %s" % key)
  
  def FdtJsonParse(buf):
      """Import FDT from JSON representation, see JSONDeviceTree.md for
         structure and encoding
         Returns an Fdt object
      """
      tree = json.loads(buf)
  
      root = FdtNode('/')
  
      _add_json_to_fdtnode(root, tree)
  
      fdt = Fdt()
      fdt.add_rootnode(root)
      return fdt
  
  def FdtFsParse(path):
      """Parse device tree filesystem and return a Fdt instance
         Should be /proc/device-tree on a device, or the fusemount.py
         mount point.
      """
      root = FdtNode("/")
  
      if path.endswith('/'):
          path = path[:-1]
  
      nodes = {path: root}
  
      for subpath, subdirs, files in os.walk(path):
          if subpath not in nodes.keys():
              raise Exception("os.walk error")
          cur = nodes[subpath]
          for f in files:
              with open(subpath+'/'+f, 'rb') as content_file:
                  content = content_file.read()
              prop = FdtProperty.new_raw_property(f, content)
              cur.add_subnode(prop)
          for subdir in subdirs:
              subnode = FdtNode(subdir)
              cur.add_subnode(subnode)
              subnode.set_parent_node(cur)
              nodes[subpath+'/'+subdir] = subnode
      
      fdt = Fdt()
      fdt.add_rootnode(root)
      return fdt
  
  class FdtBlobParse(object):  # pylint: disable-msg=R0903
      """Parse from file input"""
  
      __fdt_header_format = ">IIIIIII"
      __fdt_header_names = ('magic', 'totalsize', 'off_dt_struct',
                            'off_dt_strings', 'off_mem_rsvmap', 'version',
                            'last_comp_version')
  
      __fdt_reserve_entry_format = ">QQ"
      __fdt_reserve_entry_names = ('address', 'size')
  
      __fdt_dt_cell_format = ">I"
      __fdt_dt_prop_format = ">II"
      __fdt_dt_tag_name = {FDT_BEGIN_NODE: 'node_begin',
                           FDT_END_NODE: 'node_end',
                           FDT_PROP: 'prop',
                           FDT_NOP: 'nop',
                           FDT_END: 'end'}
  
      def __extract_fdt_header(self):
          """Extract DTB header"""
          header = Struct(self.__fdt_header_format)
          header_entry = Struct(">I")
          data = self.infile.read(header.size)
          result = dict(zip(self.__fdt_header_names, header.unpack_from(data)))
          if result['version'] >= 2:
              data = self.infile.read(header_entry.size)
              result['boot_cpuid_phys'] = header_entry.unpack_from(data)[0]
          if result['version'] >= 3:
              data = self.infile.read(header_entry.size)
              result['size_dt_strings'] = header_entry.unpack_from(data)[0]
          if result['version'] >= 17:
              data = self.infile.read(header_entry.size)
              result['size_dt_struct'] = header_entry.unpack_from(data)[0]
          return result
  
      def __extract_fdt_reserve_entries(self):
          """Extract reserved memory entries"""
          header = Struct(self.__fdt_reserve_entry_format)
          entries = []
          self.infile.seek(self.fdt_header['off_mem_rsvmap'])
          while True:
              data = self.infile.read(header.size)
              result = dict(zip(self.__fdt_reserve_entry_names,
                                header.unpack_from(data)))
              if result['address'] == 0 and result['size'] == 0:
                  return entries
              entries.append(result)
  
      def __extract_fdt_nodename(self):
          """Extract node name"""
          data = ''
          pos = self.infile.tell()
          while True:
              byte = self.infile.read(1)
              if ord(byte) == 0:
                  break
              data += byte.decode('ascii')
          align_pos = pos + len(data) + 1
          align_pos = (((align_pos) + ((4) - 1)) & ~((4) - 1))
          self.infile.seek(align_pos)
          return data
  
      def __extract_fdt_string(self, prop_string_pos):
          """Extract string from string pool"""
          data = ''
          pos = self.infile.tell()
          self.infile.seek(self.fdt_header['off_dt_strings']+prop_string_pos)
          while True:
              byte = self.infile.read(1)
              if ord(byte) == 0:
                  break
              data += byte.decode('ascii')
          self.infile.seek(pos)
          return data
  
      def __extract_fdt_prop(self):
          """Extract property"""
          prop = Struct(self.__fdt_dt_prop_format)
          pos = self.infile.tell()
          data = self.infile.read(prop.size)
          (prop_size, prop_string_pos,) = prop.unpack_from(data)
  
          prop_start = pos + prop.size
          if self.fdt_header['version'] < 16 and prop_size >= 8:
              prop_start = (((prop_start) + ((8) - 1)) & ~((8) - 1))
  
          self.infile.seek(prop_start)
          value = self.infile.read(prop_size)
  
          align_pos = self.infile.tell()
          align_pos = (((align_pos) + ((4) - 1)) & ~((4) - 1))
          self.infile.seek(align_pos)
  
          return (self.__extract_fdt_string(prop_string_pos), value)
  
      def __extract_fdt_dt(self):
          """Extract tags"""
          cell = Struct(self.__fdt_dt_cell_format)
          tags = []
          self.infile.seek(self.fdt_header['off_dt_struct'])
          while True:
              data = self.infile.read(cell.size)
              if len(data) < cell.size:
                  break
              tag, = cell.unpack_from(data)
              # print "*** %s" % self.__fdt_dt_tag_name.get(tag, '')
              if self.__fdt_dt_tag_name.get(tag, '') in 'node_begin':
                  name = self.__extract_fdt_nodename()
                  if len(name) == 0:
                      name = '/'
                  tags.append((tag, name))
              elif self.__fdt_dt_tag_name.get(tag, '') in ('node_end', 'nop'):
                  tags.append((tag, ''))
              elif self.__fdt_dt_tag_name.get(tag, '') in 'end':
                  tags.append((tag, ''))
                  break
              elif self.__fdt_dt_tag_name.get(tag, '') in 'prop':
                  propdata = self.__extract_fdt_prop()
                  tags.append((tag, propdata))
              else:
                  print("Unknown Tag %d" % tag)
          return tags
  
      def __init__(self, infile):
          """Init with file input"""
          self.infile = infile
          self.fdt_header = self.__extract_fdt_header()
          if self.fdt_header['magic'] != FDT_MAGIC:
              raise Exception('Invalid Magic')
          if self.fdt_header['version'] > FDT_MAX_VERSION:
              raise Exception('Invalid Version %d' % self.fdt_header['version'])
          if self.fdt_header['last_comp_version'] > FDT_MAX_VERSION-1:
              raise Exception('Invalid last compatible Version %d' %
                              self.fdt_header['last_comp_version'])
          self.fdt_reserve_entries = self.__extract_fdt_reserve_entries()
          self.fdt_dt_tags = self.__extract_fdt_dt()
  
      def __to_nodes(self):
          """Represent fdt as Node and properties structure
             Returns a set with the pre-node Nops, the Root Node,
              and the post-node Nops.
          """
          prenops = []
          postnops = []
          rootnode = None
          curnode = None
          for tag in self.fdt_dt_tags:
              if self.__fdt_dt_tag_name.get(tag[0], '') in 'node_begin':
                  newnode = FdtNode(tag[1])
                  if rootnode is None:
                      rootnode = newnode
                  if curnode is not None:
                      curnode.add_subnode(newnode)
                      newnode.set_parent_node(curnode)
                  curnode = newnode
              elif self.__fdt_dt_tag_name.get(tag[0], '') in 'node_end':
                  if curnode is not None:
                      curnode = curnode.get_parent_node()
              elif self.__fdt_dt_tag_name.get(tag[0], '') in 'nop':
                  if curnode is not None:
                      curnode.add_subnode(FdtNop())
                  elif rootnode is not None:
                      postnops.append(FdtNop())
                  else:
                      prenops.append(FdtNop())
              elif self.__fdt_dt_tag_name.get(tag[0], '') in 'prop':
                  if curnode is not None:
                      curnode.add_raw_attribute(tag[1][0], tag[1][1])
              elif self.__fdt_dt_tag_name.get(tag[0], '') in 'end':
                  continue
          return (prenops, rootnode, postnops)
  
      def to_fdt(self):
          """Create a fdt object
              Returns a Fdt object
          """
          if self.fdt_header['version'] >= 2:
              boot_cpuid_phys = self.fdt_header['boot_cpuid_phys']
          else:
              boot_cpuid_phys = 0
          fdt = Fdt(version=self.fdt_header['version'],
                    last_comp_version=self.fdt_header['last_comp_version'],
                    boot_cpuid_phys=boot_cpuid_phys)
          (prenops, rootnode, postnops) = self.__to_nodes()
          fdt.add_rootnode(rootnode, prenops=prenops, postnops=postnops)
          fdt.add_reserve_entries(self.fdt_reserve_entries)
          return fdt
  