tools/fat16copy.py - platform/build - Gitiles

 #!/usr/bin/env python
 #
 # Copyright 2016 The Android Open Source Project
 #
 # 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.

 import os
 import sys
 import struct

 FAT_TABLE_START = 0x200
 DEL_MARKER = 0xe5
 ESCAPE_DEL_MARKER = 0x05

 ATTRIBUTE_READ_ONLY = 0x1
 ATTRIBUTE_HIDDEN = 0x2
 ATTRIBUTE_SYSTEM = 0x4
 ATTRIBUTE_VOLUME_LABEL = 0x8
 ATTRIBUTE_SUBDIRECTORY = 0x10
 ATTRIBUTE_ARCHIVE = 0x20
 ATTRIBUTE_DEVICE = 0x40

 LFN_ATTRIBUTES = \
     ATTRIBUTE_VOLUME_LABEL | \
     ATTRIBUTE_SYSTEM | \
     ATTRIBUTE_HIDDEN | \
     ATTRIBUTE_READ_ONLY
 LFN_ATTRIBUTES_BYTE = struct.pack("B", LFN_ATTRIBUTES)

 MAX_CLUSTER_ID = 0x7FFF

 def read_le_short(f):
   "Read a little-endian 2-byte integer from the given file-like object"
   return struct.unpack("<H", f.read(2))[0]

 def read_le_long(f):
   "Read a little-endian 4-byte integer from the given file-like object"
   return struct.unpack("<L", f.read(4))[0]

 def read_byte(f):
   "Read a 1-byte integer from the given file-like object"
   return struct.unpack("B", f.read(1))[0]

 def skip_bytes(f, n):
   "Fast-forward the given file-like object by n bytes"
   f.seek(n, os.SEEK_CUR)

 def skip_short(f):
   "Fast-forward the given file-like object 2 bytes"
   skip_bytes(f, 2)

 def skip_byte(f):
   "Fast-forward the given file-like object 1 byte"
   skip_bytes(f, 1)

 def rewind_bytes(f, n):
   "Rewind the given file-like object n bytes"
   skip_bytes(f, -n)

 def rewind_short(f):
   "Rewind the given file-like object 2 bytes"
   rewind_bytes(f, 2)

 class fake_file(object):
   """
   Interface for python file-like objects that we use to manipulate the image.
   Inheritors must have an idx member which indicates the file pointer, and a
   size member which indicates the total file size.
   """

   def seek(self, amount, direction=0):
     "Implementation of seek from python's file-like object interface."
     if direction == os.SEEK_CUR:
       self.idx += amount
     elif direction == os.SEEK_END:
       self.idx = self.size - amount
     else:
       self.idx = amount

     if self.idx < 0:
       self.idx = 0
     if self.idx > self.size:
       self.idx = self.size

 class fat_file(fake_file):
   """
   A file inside of our fat image. The file may or may not have a dentry, and
   if it does this object knows nothing about it. All we see is a valid cluster
   chain.
   """

   def __init__(self, fs, cluster, size=None):
     """
     fs: The fat() object for the image this file resides in.
     cluster: The first cluster of data for this file.
     size: The size of this file. If not given, we use the total length of the
           cluster chain that starts from the cluster argument.
     """
     self.fs = fs
     self.start_cluster = cluster
     self.size = size

     if self.size is None:
       self.size = fs.get_chain_size(cluster)

     self.idx = 0

   def read(self, size):
     "Read method for pythonic file-like interface."
     if self.idx + size > self.size:
       size = self.size - self.idx
     got = self.fs.read_file(self.start_cluster, self.idx, size)
     self.idx += len(got)
     return got

   def write(self, data):
     "Write method for pythonic file-like interface."
     self.fs.write_file(self.start_cluster, self.idx, data)
     self.idx += len(data)

     if self.idx > self.size:
       self.size = self.idx

 def shorten(name, index):
   """
   Create a file short name from the given long name (with the extension already
   removed). The index argument gives a disambiguating integer to work into the
   name to avoid collisions.
   """
   name = "".join(name.split('.')).upper()
   postfix = "~" + str(index)
   return name[:8 - len(postfix)] + postfix

 class fat_dir(object):
   "A directory in our fat filesystem."

   def __init__(self, backing):
     """
     backing: A file-like object from which we can read dentry info. Should have
     an fs member allowing us to get to the underlying image.
     """
     self.backing = backing
     self.dentries = []
     to_read = self.backing.size / 32

     self.backing.seek(0)

     while to_read > 0:
       (dent, consumed) = self.backing.fs.read_dentry(self.backing)
       to_read -= consumed

       if dent:
         self.dentries.append(dent)

   def __str__(self):
     return "\n".join([str(x) for x in self.dentries]) + "\n"

   def add_dentry(self, attributes, shortname, ext, longname, first_cluster,
       size):
     """
     Add a new dentry to this directory.
     attributes: Attribute flags for this dentry. See the ATTRIBUTE_ constants
                 above.
     shortname: Short name of this file. Up to 8 characters, no dots.
     ext: Extension for this file. Up to 3 characters, no dots.
     longname: The long name for this file, with extension. Largely unrestricted.
     first_cluster: The first cluster in the cluster chain holding the contents
                    of this file.
     size: The size of this file. Set to 0 for subdirectories.
     """
     new_dentry = dentry(self.backing.fs, attributes, shortname, ext,
         longname, first_cluster, size)
     new_dentry.commit(self.backing)
     self.dentries.append(new_dentry)
     return new_dentry

   def make_short_name(self, name):
     """
     Given a long file name, return an 8.3 short name as a tuple. Name will be
     engineered not to collide with other such names in this folder.
     """
     parts = name.rsplit('.', 1)

     if len(parts) == 1:
       parts.append('')

     name = parts[0]
     ext = parts[1].upper()

     index = 1
     shortened = shorten(name, index)

     for dent in self.dentries:
       assert dent.longname != name, "File must not exist"
       if dent.shortname == shortened:
         index += 1
         shortened = shorten(name, index)

     if len(name) <= 8 and len(ext) <= 3 and not '.' in name:
       return (name.upper().ljust(8), ext.ljust(3))

     return (shortened.ljust(8), ext[:3].ljust(3))

   def new_file(self, name, data=None):
     """
     Add a new regular file to this directory.
     name: The name of the new file.
     data: The contents of the new file. Given as a file-like object.
     """
     size = 0
     if data:
       data.seek(0, os.SEEK_END)
       size = data.tell()

     # Empty files shouldn't have any clusters assigned.
     chunk = self.backing.fs.allocate(size) if size > 0 else 0
     (shortname, ext) = self.make_short_name(name)
     self.add_dentry(0, shortname, ext, name, chunk, size)

     if data is None:
       return

     data_file = fat_file(self.backing.fs, chunk, size)
     data.seek(0)
     data_file.write(data.read())

   def open_subdirectory(self, name):
     """
     Open a subdirectory of this directory with the given name. If the
     subdirectory doesn't exist, a new one is created instead.
     Returns a fat_dir().
     """
     for dent in self.dentries:
       if dent.longname == name:
         return dent.open_directory()

     chunk = self.backing.fs.allocate(1)
     (shortname, ext) = self.make_short_name(name)
     new_dentry = self.add_dentry(ATTRIBUTE_SUBDIRECTORY, shortname,
             ext, name, chunk, 0)
     result = new_dentry.open_directory()

     parent_cluster = 0

     if hasattr(self.backing, 'start_cluster'):
       parent_cluster = self.backing.start_cluster

     result.add_dentry(ATTRIBUTE_SUBDIRECTORY, '.', '', '', chunk, 0)
     result.add_dentry(ATTRIBUTE_SUBDIRECTORY, '..', '', '', parent_cluster, 0)

     return result

 def lfn_checksum(name_data):
   """
   Given the characters of an 8.3 file name (concatenated *without* the dot),
   Compute a one-byte checksum which needs to appear in corresponding long file
   name entries.
   """
   assert len(name_data) == 11, "Name data should be exactly 11 characters"
   name_data = struct.unpack("B" * 11, name_data)

   result = 0

   for char in name_data:
     last_bit = (result & 1) << 7
     result = (result >> 1) | last_bit
     result += char
     result = result & 0xFF

   return struct.pack("B", result)

 class dentry(object):
   "A directory entry"
   def __init__(self, fs, attributes, shortname, ext, longname,
       first_cluster, size):
     """
     fs: The fat() object for the image we're stored in.
     attributes: The attribute flags for this dentry. See the ATTRIBUTE_ flags
                 above.
     shortname: The short name stored in this dentry. Up to 8 characters, no
                dots.
     ext: The file extension stored in this dentry. Up to 3 characters, no
          dots.
     longname: The long file name stored in this dentry.
     first_cluster: The first cluster in the cluster chain backing the file
                    this dentry points to.
     size: Size of the file this dentry points to. 0 for subdirectories.
     """
     self.fs = fs
     self.attributes = attributes
     self.shortname = shortname
     self.ext = ext
     self.longname = longname
     self.first_cluster = first_cluster
     self.size = size

   def name(self):
     "A friendly text file name for this dentry."
     if self.longname:
       return self.longname

     if not self.ext or len(self.ext) == 0:
       return self.shortname

     return self.shortname + "." + self.ext

   def __str__(self):
     return self.name() + " (" + str(self.size) + \
       " bytes @ " + str(self.first_cluster) + ")"

   def is_directory(self):
     "Return whether this dentry points to a directory."
     return (self.attributes & ATTRIBUTE_SUBDIRECTORY) != 0

   def open_file(self):
     "Open the target of this dentry if it is a regular file."
     assert not self.is_directory(), "Cannot open directory as file"
     return fat_file(self.fs, self.first_cluster, self.size)

   def open_directory(self):
     "Open the target of this dentry if it is a directory."
     assert self.is_directory(), "Cannot open file as directory"
     return fat_dir(fat_file(self.fs, self.first_cluster))

   def longname_records(self, checksum):
     """
     Get the longname records necessary to store this dentry's long name,
     packed as a series of 32-byte strings.
     """
     if self.longname is None:
       return []
     if len(self.longname) == 0:
       return []

     encoded_long_name = self.longname.encode('utf-16-le')
     long_name_padding = "\0" * (26 - (len(encoded_long_name) % 26))
     padded_long_name = encoded_long_name + long_name_padding

     chunks = [padded_long_name[i:i+26] for i in range(0,
       len(padded_long_name), 26)]
     records = []
     sequence_number = 1

     for c in chunks:
       sequence_byte = struct.pack("B", sequence_number)
       sequence_number += 1
       record = sequence_byte + c[:10] + LFN_ATTRIBUTES_BYTE + "\0" + \
           checksum + c[10:22] + "\0\0" + c[22:]
       records.append(record)

     last = records.pop()
     last_seq = struct.unpack("B", last[0])[0]
     last_seq = last_seq | 0x40
     last = struct.pack("B", last_seq) + last[1:]
     records.append(last)
     records.reverse()

     return records

   def commit(self, f):
     """
     Write this dentry into the given file-like object,
     which is assumed to contain a FAT directory.
     """
     f.seek(0)
     padded_short_name = self.shortname.ljust(8)
     padded_ext = self.ext.ljust(3)
     name_data = padded_short_name + padded_ext
     longname_record_data = self.longname_records(lfn_checksum(name_data))
     record = struct.pack("<11sBBBHHHHHHHL",
         name_data,
         self.attributes,
         0,
         0,
         0,
         0,
         0,
         0,
         0,
         0,
         self.first_cluster,
         self.size)
     entry = "".join(longname_record_data + [record])

     record_count = len(longname_record_data) + 1

     found_count = 0
     while found_count < record_count:
       record = f.read(32)

       if record is None or len(record) != 32:
         # We reached the EOF, so we need to extend the file with a new cluster.
         f.write("\0" * self.fs.bytes_per_cluster)
         f.seek(-self.fs.bytes_per_cluster, os.SEEK_CUR)
         record = f.read(32)

       marker = struct.unpack("B", record[0])[0]

       if marker == DEL_MARKER or marker == 0:
         found_count += 1
       else:
         found_count = 0

     f.seek(-(record_count * 32), os.SEEK_CUR)
     f.write(entry)

 class root_dentry_file(fake_file):
   """
   File-like object for the root directory. The root directory isn't stored in a
   normal file, so we can't use a normal fat_file object to create a view of it.
   """
   def __init__(self, fs):
     self.fs = fs
     self.idx = 0
     self.size = fs.root_entries * 32

   def read(self, count):
     f = self.fs.f
     f.seek(self.fs.data_start() + self.idx)

     if self.idx + count > self.size:
       count = self.size - self.idx

     ret = f.read(count)
     self.idx += len(ret)
     return ret

   def write(self, data):
     f = self.fs.f
     f.seek(self.fs.data_start() + self.idx)

     if self.idx + len(data) > self.size:
       data = data[:self.size - self.idx]

     f.write(data)
     self.idx += len(data)
     if self.idx > self.size:
       self.size = self.idx

 class fat(object):
   "A FAT image"

   def __init__(self, path):
     """
     path: Path to an image file containing a FAT file system.
     """
     f = open(path, "r+b")

     self.f = f

     f.seek(0xb)
     bytes_per_sector = read_le_short(f)
     sectors_per_cluster = read_byte(f)

     self.bytes_per_cluster = bytes_per_sector * sectors_per_cluster

     reserved_sectors = read_le_short(f)
     assert reserved_sectors == 1, \
         "Can only handle FAT with 1 reserved sector"

     fat_count = read_byte(f)
     assert fat_count == 2, "Can only handle FAT with 2 tables"

     self.root_entries = read_le_short(f)

     skip_short(f) # Image size. Sort of. Useless field.
     skip_byte(f) # Media type. We don't care.

     self.fat_size = read_le_short(f) * bytes_per_sector
     self.root = fat_dir(root_dentry_file(self))

   def data_start(self):
     """
     Index of the first byte after the FAT tables.
     """
     return FAT_TABLE_START + self.fat_size * 2

   def get_chain_size(self, head_cluster):
     """
     Return how many total bytes are in the cluster chain rooted at the given
     cluster.
     """
     if head_cluster == 0:
       return 0

     f = self.f
     f.seek(FAT_TABLE_START + head_cluster * 2)

     cluster_count = 0

     while head_cluster <= MAX_CLUSTER_ID:
       cluster_count += 1
       head_cluster = read_le_short(f)
       f.seek(FAT_TABLE_START + head_cluster * 2)

     return cluster_count * self.bytes_per_cluster

   def read_dentry(self, f=None):
     """
     Read and decode a dentry from the given file-like object at its current
     seek position.
     """
     f = f or self.f
     attributes = None

     consumed = 1

     lfn_entries = {}

     while True:
       skip_bytes(f, 11)
       attributes = read_byte(f)
       rewind_bytes(f, 12)

       if attributes & LFN_ATTRIBUTES != LFN_ATTRIBUTES:
         break

       consumed += 1

       seq = read_byte(f)
       chars = f.read(10)
       skip_bytes(f, 3) # Various hackish nonsense
       chars += f.read(12)
       skip_short(f) # Lots more nonsense
       chars += f.read(4)

       chars = unicode(chars, "utf-16-le").encode("utf-8")

       lfn_entries[seq] = chars

     ind = read_byte(f)

     if ind == 0 or ind == DEL_MARKER:
       skip_bytes(f, 31)
       return (None, consumed)

     if ind == ESCAPE_DEL_MARKER:
       ind = DEL_MARKER

     ind = str(unichr(ind))

     if ind == '.':
       skip_bytes(f, 31)
       return (None, consumed)

     shortname = ind + f.read(7).rstrip()
     ext = f.read(3).rstrip()
     skip_bytes(f, 15) # Assorted flags, ctime/atime/mtime, etc.
     first_cluster = read_le_short(f)
     size = read_le_long(f)

     lfn = lfn_entries.items()
     lfn.sort(key=lambda x: x[0])
     lfn = reduce(lambda x, y: x + y[1], lfn, "")

     if len(lfn) == 0:
       lfn = None
     else:
       lfn = lfn.split('\0', 1)[0]

     return (dentry(self, attributes, shortname, ext, lfn, first_cluster,
       size), consumed)

   def read_file(self, head_cluster, start_byte, size):
     """
     Read from a given FAT file.
     head_cluster: The first cluster in the file.
     start_byte: How many bytes in to the file to begin the read.
     size: How many bytes to read.
     """
     f = self.f

     assert size >= 0, "Can't read a negative amount"
     if size == 0:
       return ""

     got_data = ""

     while True:
       size_now = size
       if start_byte + size > self.bytes_per_cluster:
         size_now = self.bytes_per_cluster - start_byte

       if start_byte < self.bytes_per_cluster:
         size -= size_now

         cluster_bytes_from_root = (head_cluster - 2) * \
             self.bytes_per_cluster
         bytes_from_root = cluster_bytes_from_root + start_byte
         bytes_from_data_start = bytes_from_root + self.root_entries * 32

         f.seek(self.data_start() + bytes_from_data_start)
         line = f.read(size_now)
         got_data += line

         if size == 0:
           return got_data

       start_byte -= self.bytes_per_cluster

       if start_byte < 0:
         start_byte = 0

       f.seek(FAT_TABLE_START + head_cluster * 2)
       assert head_cluster <= MAX_CLUSTER_ID, "Out-of-bounds read"
       head_cluster = read_le_short(f)
       assert head_cluster > 0, "Read free cluster"

     return got_data

   def write_cluster_entry(self, entry):
     """
     Write a cluster entry to the FAT table. Assumes our backing file is already
     seeked to the correct entry in the first FAT table.
     """
     f = self.f
     f.write(struct.pack("<H", entry))
     skip_bytes(f, self.fat_size - 2)
     f.write(struct.pack("<H", entry))
     rewind_bytes(f, self.fat_size)

   def allocate(self, amount):
     """
     Allocate a new cluster chain big enough to hold at least the given amount
     of bytes.
     """
     assert amount > 0, "Must allocate a non-zero amount."

     f = self.f
     f.seek(FAT_TABLE_START + 4)

     current = None
     current_size = 0
     free_zones = {}

     pos = 2
     while pos < self.fat_size / 2:
       data = read_le_short(f)

       if data == 0 and current is not None:
         current_size += 1
       elif data == 0:
         current = pos
         current_size = 1
       elif current is not None:
         free_zones[current] = current_size
         current = None

       pos += 1

     if current is not None:
       free_zones[current] = current_size

     free_zones = free_zones.items()
     free_zones.sort(key=lambda x: x[1])

     grabbed_zones = []
     grabbed = 0

     while grabbed < amount and len(free_zones) > 0:
       zone = free_zones.pop()
       grabbed += zone[1] * self.bytes_per_cluster
       grabbed_zones.append(zone)

     if grabbed < amount:
       return None

     excess = (grabbed - amount) / self.bytes_per_cluster

     grabbed_zones[-1] = (grabbed_zones[-1][0],
         grabbed_zones[-1][1] - excess)

     out = None
     grabbed_zones.reverse()

     for cluster, size in grabbed_zones:
       entries = range(cluster + 1, cluster + size)
       entries.append(out or 0xFFFF)
       out = cluster
       f.seek(FAT_TABLE_START + cluster * 2)
       for entry in entries:
         self.write_cluster_entry(entry)

     return out

   def extend_cluster(self, cluster, amount):
     """
     Given a cluster which is the *last* cluster in a chain, extend it to hold
     at least `amount` more bytes.
     """
     if amount == 0:
       return
     f = self.f
     entry_offset = FAT_TABLE_START + cluster * 2
     f.seek(entry_offset)
     assert read_le_short(f) == 0xFFFF, "Extending from middle of chain"

     return_cluster = self.allocate(amount)
     f.seek(entry_offset)
     self.write_cluster_entry(return_cluster)
     return return_cluster

   def write_file(self, head_cluster, start_byte, data):
     """
     Write to a given FAT file.

     head_cluster: The first cluster in the file.
     start_byte: How many bytes in to the file to begin the write.
     data: The data to write.
     """
     f = self.f
     last_offset = start_byte + len(data)
     current_offset = 0
     current_cluster = head_cluster

     while current_offset < last_offset:
       # Write everything that falls in the cluster starting at current_offset.
       data_begin = max(0, current_offset - start_byte)
       data_end = min(len(data),
                      current_offset + self.bytes_per_cluster - start_byte)
       if data_end > data_begin:
         cluster_file_offset = (self.data_start() + self.root_entries * 32 +
                                (current_cluster - 2) * self.bytes_per_cluster)
         f.seek(cluster_file_offset + max(0, start_byte - current_offset))
         f.write(data[data_begin:data_end])

       # Advance to the next cluster in the chain or get a new cluster if needed.
       current_offset += self.bytes_per_cluster
       if last_offset > current_offset:
         f.seek(FAT_TABLE_START + current_cluster * 2)
         next_cluster = read_le_short(f)
         if next_cluster > MAX_CLUSTER_ID:
           next_cluster = self.extend_cluster(current_cluster, len(data))
         current_cluster = next_cluster
         assert current_cluster > 0, "Cannot write free cluster"


 def add_item(directory, item):
   """
   Copy a file into the given FAT directory. If the path given is a directory,
   copy recursively.
   directory: fat_dir to copy the file in to
   item: Path of local file to copy
   """
   if os.path.isdir(item):
     base = os.path.basename(item)
     if len(base) == 0:
       base = os.path.basename(item[:-1])
     sub = directory.open_subdirectory(base)
     for next_item in sorted(os.listdir(item)):
       add_item(sub, os.path.join(item, next_item))
   else:
     with open(item, 'rb') as f:
       directory.new_file(os.path.basename(item), f)

 if __name__ == "__main__":
   if len(sys.argv) < 3:
     print("Usage: fat16copy.py <image> <file> [<file> ...]")
     print("Files are copied into the root of the image.")
     print("Directories are copied recursively")
     sys.exit(1)

   root = fat(sys.argv[1]).root

   for p in sys.argv[2:]:
     add_item(root, p)
	#!/usr/bin/env python
	#
	# Copyright 2016 The Android Open Source Project
	#
	# 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.

	import os
	import sys
	import struct

	FAT_TABLE_START = 0x200
	DEL_MARKER = 0xe5
	ESCAPE_DEL_MARKER = 0x05

	ATTRIBUTE_READ_ONLY = 0x1
	ATTRIBUTE_HIDDEN = 0x2
	ATTRIBUTE_SYSTEM = 0x4
	ATTRIBUTE_VOLUME_LABEL = 0x8
	ATTRIBUTE_SUBDIRECTORY = 0x10
	ATTRIBUTE_ARCHIVE = 0x20
	ATTRIBUTE_DEVICE = 0x40

	LFN_ATTRIBUTES = \
	ATTRIBUTE_VOLUME_LABEL \| \
	ATTRIBUTE_SYSTEM \| \
	ATTRIBUTE_HIDDEN \| \
	ATTRIBUTE_READ_ONLY
	LFN_ATTRIBUTES_BYTE = struct.pack("B", LFN_ATTRIBUTES)

	MAX_CLUSTER_ID = 0x7FFF

	def read_le_short(f):
	"Read a little-endian 2-byte integer from the given file-like object"
	return struct.unpack("<H", f.read(2))[0]

	def read_le_long(f):
	"Read a little-endian 4-byte integer from the given file-like object"
	return struct.unpack("<L", f.read(4))[0]

	def read_byte(f):
	"Read a 1-byte integer from the given file-like object"
	return struct.unpack("B", f.read(1))[0]

	def skip_bytes(f, n):
	"Fast-forward the given file-like object by n bytes"
	f.seek(n, os.SEEK_CUR)

	def skip_short(f):
	"Fast-forward the given file-like object 2 bytes"
	skip_bytes(f, 2)

	def skip_byte(f):
	"Fast-forward the given file-like object 1 byte"
	skip_bytes(f, 1)

	def rewind_bytes(f, n):
	"Rewind the given file-like object n bytes"
	skip_bytes(f, -n)

	def rewind_short(f):
	"Rewind the given file-like object 2 bytes"
	rewind_bytes(f, 2)

	class fake_file(object):
	"""
	Interface for python file-like objects that we use to manipulate the image.
	Inheritors must have an idx member which indicates the file pointer, and a
	size member which indicates the total file size.
	"""

	def seek(self, amount, direction=0):
	"Implementation of seek from python's file-like object interface."
	if direction == os.SEEK_CUR:
	self.idx += amount
	elif direction == os.SEEK_END:
	self.idx = self.size - amount
	else:
	self.idx = amount

	if self.idx < 0:
	self.idx = 0
	if self.idx > self.size:
	self.idx = self.size

	class fat_file(fake_file):
	"""
	A file inside of our fat image. The file may or may not have a dentry, and
	if it does this object knows nothing about it. All we see is a valid cluster
	chain.
	"""

	def __init__(self, fs, cluster, size=None):
	"""
	fs: The fat() object for the image this file resides in.
	cluster: The first cluster of data for this file.
	size: The size of this file. If not given, we use the total length of the
	cluster chain that starts from the cluster argument.
	"""
	self.fs = fs
	self.start_cluster = cluster
	self.size = size

	if self.size is None:
	self.size = fs.get_chain_size(cluster)

	self.idx = 0

	def read(self, size):
	"Read method for pythonic file-like interface."
	if self.idx + size > self.size:
	size = self.size - self.idx
	got = self.fs.read_file(self.start_cluster, self.idx, size)
	self.idx += len(got)
	return got

	def write(self, data):
	"Write method for pythonic file-like interface."
	self.fs.write_file(self.start_cluster, self.idx, data)
	self.idx += len(data)

	if self.idx > self.size:
	self.size = self.idx

	def shorten(name, index):
	"""
	Create a file short name from the given long name (with the extension already
	removed). The index argument gives a disambiguating integer to work into the
	name to avoid collisions.
	"""
	name = "".join(name.split('.')).upper()
	postfix = "~" + str(index)
	return name[:8 - len(postfix)] + postfix

	class fat_dir(object):
	"A directory in our fat filesystem."

	def __init__(self, backing):
	"""
	backing: A file-like object from which we can read dentry info. Should have
	an fs member allowing us to get to the underlying image.
	"""
	self.backing = backing
	self.dentries = []
	to_read = self.backing.size / 32

	self.backing.seek(0)

	while to_read > 0:
	(dent, consumed) = self.backing.fs.read_dentry(self.backing)
	to_read -= consumed

	if dent:
	self.dentries.append(dent)

	def __str__(self):
	return "\n".join([str(x) for x in self.dentries]) + "\n"

	def add_dentry(self, attributes, shortname, ext, longname, first_cluster,
	size):
	"""
	Add a new dentry to this directory.
	attributes: Attribute flags for this dentry. See the ATTRIBUTE_ constants
	above.
	shortname: Short name of this file. Up to 8 characters, no dots.
	ext: Extension for this file. Up to 3 characters, no dots.
	longname: The long name for this file, with extension. Largely unrestricted.
	first_cluster: The first cluster in the cluster chain holding the contents
	of this file.
	size: The size of this file. Set to 0 for subdirectories.
	"""
	new_dentry = dentry(self.backing.fs, attributes, shortname, ext,
	longname, first_cluster, size)
	new_dentry.commit(self.backing)
	self.dentries.append(new_dentry)
	return new_dentry

	def make_short_name(self, name):
	"""
	Given a long file name, return an 8.3 short name as a tuple. Name will be
	engineered not to collide with other such names in this folder.
	"""
	parts = name.rsplit('.', 1)

	if len(parts) == 1:
	parts.append('')

	name = parts[0]
	ext = parts[1].upper()

	index = 1
	shortened = shorten(name, index)

	for dent in self.dentries:
	assert dent.longname != name, "File must not exist"
	if dent.shortname == shortened:
	index += 1
	shortened = shorten(name, index)

	if len(name) <= 8 and len(ext) <= 3 and not '.' in name:
	return (name.upper().ljust(8), ext.ljust(3))

	return (shortened.ljust(8), ext[:3].ljust(3))

	def new_file(self, name, data=None):
	"""
	Add a new regular file to this directory.
	name: The name of the new file.
	data: The contents of the new file. Given as a file-like object.
	"""
	size = 0
	if data:
	data.seek(0, os.SEEK_END)
	size = data.tell()

	# Empty files shouldn't have any clusters assigned.
	chunk = self.backing.fs.allocate(size) if size > 0 else 0
	(shortname, ext) = self.make_short_name(name)
	self.add_dentry(0, shortname, ext, name, chunk, size)

	if data is None:
	return

	data_file = fat_file(self.backing.fs, chunk, size)
	data.seek(0)
	data_file.write(data.read())

	def open_subdirectory(self, name):
	"""
	Open a subdirectory of this directory with the given name. If the
	subdirectory doesn't exist, a new one is created instead.
	Returns a fat_dir().
	"""
	for dent in self.dentries:
	if dent.longname == name:
	return dent.open_directory()

	chunk = self.backing.fs.allocate(1)
	(shortname, ext) = self.make_short_name(name)
	new_dentry = self.add_dentry(ATTRIBUTE_SUBDIRECTORY, shortname,
	ext, name, chunk, 0)
	result = new_dentry.open_directory()

	parent_cluster = 0

	if hasattr(self.backing, 'start_cluster'):
	parent_cluster = self.backing.start_cluster

	result.add_dentry(ATTRIBUTE_SUBDIRECTORY, '.', '', '', chunk, 0)
	result.add_dentry(ATTRIBUTE_SUBDIRECTORY, '..', '', '', parent_cluster, 0)

	return result

	def lfn_checksum(name_data):
	"""
	Given the characters of an 8.3 file name (concatenated without the dot),
	Compute a one-byte checksum which needs to appear in corresponding long file
	name entries.
	"""
	assert len(name_data) == 11, "Name data should be exactly 11 characters"
	name_data = struct.unpack("B" * 11, name_data)

	result = 0

	for char in name_data:
	last_bit = (result & 1) << 7
	result = (result >> 1) \| last_bit
	result += char
	result = result & 0xFF

	return struct.pack("B", result)

	class dentry(object):
	"A directory entry"
	def __init__(self, fs, attributes, shortname, ext, longname,
	first_cluster, size):
	"""
	fs: The fat() object for the image we're stored in.
	attributes: The attribute flags for this dentry. See the ATTRIBUTE_ flags
	above.
	shortname: The short name stored in this dentry. Up to 8 characters, no
	dots.
	ext: The file extension stored in this dentry. Up to 3 characters, no
	dots.
	longname: The long file name stored in this dentry.
	first_cluster: The first cluster in the cluster chain backing the file
	this dentry points to.
	size: Size of the file this dentry points to. 0 for subdirectories.
	"""
	self.fs = fs
	self.attributes = attributes
	self.shortname = shortname
	self.ext = ext
	self.longname = longname
	self.first_cluster = first_cluster
	self.size = size

	def name(self):
	"A friendly text file name for this dentry."
	if self.longname:
	return self.longname

	if not self.ext or len(self.ext) == 0:
	return self.shortname

	return self.shortname + "." + self.ext

	def __str__(self):
	return self.name() + " (" + str(self.size) + \
	" bytes @ " + str(self.first_cluster) + ")"

	def is_directory(self):
	"Return whether this dentry points to a directory."
	return (self.attributes & ATTRIBUTE_SUBDIRECTORY) != 0

	def open_file(self):
	"Open the target of this dentry if it is a regular file."
	assert not self.is_directory(), "Cannot open directory as file"
	return fat_file(self.fs, self.first_cluster, self.size)

	def open_directory(self):
	"Open the target of this dentry if it is a directory."
	assert self.is_directory(), "Cannot open file as directory"
	return fat_dir(fat_file(self.fs, self.first_cluster))

	def longname_records(self, checksum):
	"""
	Get the longname records necessary to store this dentry's long name,
	packed as a series of 32-byte strings.
	"""
	if self.longname is None:
	return []
	if len(self.longname) == 0:
	return []

	encoded_long_name = self.longname.encode('utf-16-le')
	long_name_padding = "\0" * (26 - (len(encoded_long_name) % 26))
	padded_long_name = encoded_long_name + long_name_padding

	chunks = [padded_long_name[i:i+26] for i in range(0,
	len(padded_long_name), 26)]
	records = []
	sequence_number = 1

	for c in chunks:
	sequence_byte = struct.pack("B", sequence_number)
	sequence_number += 1
	record = sequence_byte + c[:10] + LFN_ATTRIBUTES_BYTE + "\0" + \
	checksum + c[10:22] + "\0\0" + c[22:]
	records.append(record)

	last = records.pop()
	last_seq = struct.unpack("B", last[0])[0]
	last_seq = last_seq \| 0x40
	last = struct.pack("B", last_seq) + last[1:]
	records.append(last)
	records.reverse()

	return records

	def commit(self, f):
	"""
	Write this dentry into the given file-like object,
	which is assumed to contain a FAT directory.
	"""
	f.seek(0)
	padded_short_name = self.shortname.ljust(8)
	padded_ext = self.ext.ljust(3)
	name_data = padded_short_name + padded_ext
	longname_record_data = self.longname_records(lfn_checksum(name_data))
	record = struct.pack("<11sBBBHHHHHHHL",
	name_data,
	self.attributes,
	0,
	0,
	0,
	0,
	0,
	0,
	0,
	0,
	self.first_cluster,
	self.size)
	entry = "".join(longname_record_data + [record])

	record_count = len(longname_record_data) + 1

	found_count = 0
	while found_count < record_count:
	record = f.read(32)

	if record is None or len(record) != 32:
	# We reached the EOF, so we need to extend the file with a new cluster.
	f.write("\0" * self.fs.bytes_per_cluster)
	f.seek(-self.fs.bytes_per_cluster, os.SEEK_CUR)
	record = f.read(32)

	marker = struct.unpack("B", record[0])[0]

	if marker == DEL_MARKER or marker == 0:
	found_count += 1
	else:
	found_count = 0

	f.seek(-(record_count * 32), os.SEEK_CUR)
	f.write(entry)

	class root_dentry_file(fake_file):
	"""
	File-like object for the root directory. The root directory isn't stored in a
	normal file, so we can't use a normal fat_file object to create a view of it.
	"""
	def __init__(self, fs):
	self.fs = fs
	self.idx = 0
	self.size = fs.root_entries * 32

	def read(self, count):
	f = self.fs.f
	f.seek(self.fs.data_start() + self.idx)

	if self.idx + count > self.size:
	count = self.size - self.idx

	ret = f.read(count)
	self.idx += len(ret)
	return ret

	def write(self, data):
	f = self.fs.f
	f.seek(self.fs.data_start() + self.idx)

	if self.idx + len(data) > self.size:
	data = data[:self.size - self.idx]

	f.write(data)
	self.idx += len(data)
	if self.idx > self.size:
	self.size = self.idx

	class fat(object):
	"A FAT image"

	def __init__(self, path):
	"""
	path: Path to an image file containing a FAT file system.
	"""
	f = open(path, "r+b")

	self.f = f

	f.seek(0xb)
	bytes_per_sector = read_le_short(f)
	sectors_per_cluster = read_byte(f)

	self.bytes_per_cluster = bytes_per_sector * sectors_per_cluster

	reserved_sectors = read_le_short(f)
	assert reserved_sectors == 1, \
	"Can only handle FAT with 1 reserved sector"

	fat_count = read_byte(f)
	assert fat_count == 2, "Can only handle FAT with 2 tables"

	self.root_entries = read_le_short(f)

	skip_short(f) # Image size. Sort of. Useless field.
	skip_byte(f) # Media type. We don't care.

	self.fat_size = read_le_short(f) * bytes_per_sector
	self.root = fat_dir(root_dentry_file(self))

	def data_start(self):
	"""
	Index of the first byte after the FAT tables.
	"""
	return FAT_TABLE_START + self.fat_size * 2

	def get_chain_size(self, head_cluster):
	"""
	Return how many total bytes are in the cluster chain rooted at the given
	cluster.
	"""
	if head_cluster == 0:
	return 0

	f = self.f
	f.seek(FAT_TABLE_START + head_cluster * 2)

	cluster_count = 0

	while head_cluster <= MAX_CLUSTER_ID:
	cluster_count += 1
	head_cluster = read_le_short(f)
	f.seek(FAT_TABLE_START + head_cluster * 2)

	return cluster_count * self.bytes_per_cluster

	def read_dentry(self, f=None):
	"""
	Read and decode a dentry from the given file-like object at its current
	seek position.
	"""
	f = f or self.f
	attributes = None

	consumed = 1

	lfn_entries = {}

	while True:
	skip_bytes(f, 11)
	attributes = read_byte(f)
	rewind_bytes(f, 12)

	if attributes & LFN_ATTRIBUTES != LFN_ATTRIBUTES:
	break

	consumed += 1

	seq = read_byte(f)
	chars = f.read(10)
	skip_bytes(f, 3) # Various hackish nonsense
	chars += f.read(12)
	skip_short(f) # Lots more nonsense
	chars += f.read(4)

	chars = unicode(chars, "utf-16-le").encode("utf-8")

	lfn_entries[seq] = chars

	ind = read_byte(f)

	if ind == 0 or ind == DEL_MARKER:
	skip_bytes(f, 31)
	return (None, consumed)

	if ind == ESCAPE_DEL_MARKER:
	ind = DEL_MARKER

	ind = str(unichr(ind))

	if ind == '.':
	skip_bytes(f, 31)
	return (None, consumed)

	shortname = ind + f.read(7).rstrip()
	ext = f.read(3).rstrip()
	skip_bytes(f, 15) # Assorted flags, ctime/atime/mtime, etc.
	first_cluster = read_le_short(f)
	size = read_le_long(f)

	lfn = lfn_entries.items()
	lfn.sort(key=lambda x: x[0])
	lfn = reduce(lambda x, y: x + y[1], lfn, "")

	if len(lfn) == 0:
	lfn = None
	else:
	lfn = lfn.split('\0', 1)[0]

	return (dentry(self, attributes, shortname, ext, lfn, first_cluster,
	size), consumed)

	def read_file(self, head_cluster, start_byte, size):
	"""
	Read from a given FAT file.
	head_cluster: The first cluster in the file.
	start_byte: How many bytes in to the file to begin the read.
	size: How many bytes to read.
	"""
	f = self.f

	assert size >= 0, "Can't read a negative amount"
	if size == 0:
	return ""

	got_data = ""

	while True:
	size_now = size
	if start_byte + size > self.bytes_per_cluster:
	size_now = self.bytes_per_cluster - start_byte

	if start_byte < self.bytes_per_cluster:
	size -= size_now

	cluster_bytes_from_root = (head_cluster - 2) * \
	self.bytes_per_cluster
	bytes_from_root = cluster_bytes_from_root + start_byte
	bytes_from_data_start = bytes_from_root + self.root_entries * 32

	f.seek(self.data_start() + bytes_from_data_start)
	line = f.read(size_now)
	got_data += line

	if size == 0:
	return got_data

	start_byte -= self.bytes_per_cluster

	if start_byte < 0:
	start_byte = 0

	f.seek(FAT_TABLE_START + head_cluster * 2)
	assert head_cluster <= MAX_CLUSTER_ID, "Out-of-bounds read"
	head_cluster = read_le_short(f)
	assert head_cluster > 0, "Read free cluster"

	return got_data

	def write_cluster_entry(self, entry):
	"""
	Write a cluster entry to the FAT table. Assumes our backing file is already
	seeked to the correct entry in the first FAT table.
	"""
	f = self.f
	f.write(struct.pack("<H", entry))
	skip_bytes(f, self.fat_size - 2)
	f.write(struct.pack("<H", entry))
	rewind_bytes(f, self.fat_size)

	def allocate(self, amount):
	"""
	Allocate a new cluster chain big enough to hold at least the given amount
	of bytes.
	"""
	assert amount > 0, "Must allocate a non-zero amount."

	f = self.f
	f.seek(FAT_TABLE_START + 4)

	current = None
	current_size = 0
	free_zones = {}

	pos = 2
	while pos < self.fat_size / 2:
	data = read_le_short(f)

	if data == 0 and current is not None:
	current_size += 1
	elif data == 0:
	current = pos
	current_size = 1
	elif current is not None:
	free_zones[current] = current_size
	current = None

	pos += 1

	if current is not None:
	free_zones[current] = current_size

	free_zones = free_zones.items()
	free_zones.sort(key=lambda x: x[1])

	grabbed_zones = []
	grabbed = 0

	while grabbed < amount and len(free_zones) > 0:
	zone = free_zones.pop()
	grabbed += zone[1] * self.bytes_per_cluster
	grabbed_zones.append(zone)

	if grabbed < amount:
	return None

	excess = (grabbed - amount) / self.bytes_per_cluster

	grabbed_zones[-1] = (grabbed_zones[-1][0],
	grabbed_zones[-1][1] - excess)

	out = None
	grabbed_zones.reverse()

	for cluster, size in grabbed_zones:
	entries = range(cluster + 1, cluster + size)
	entries.append(out or 0xFFFF)
	out = cluster
	f.seek(FAT_TABLE_START + cluster * 2)
	for entry in entries:
	self.write_cluster_entry(entry)

	return out

	def extend_cluster(self, cluster, amount):
	"""
	Given a cluster which is the last cluster in a chain, extend it to hold
	at least `amount` more bytes.
	"""
	if amount == 0:
	return
	f = self.f
	entry_offset = FAT_TABLE_START + cluster * 2
	f.seek(entry_offset)
	assert read_le_short(f) == 0xFFFF, "Extending from middle of chain"

	return_cluster = self.allocate(amount)
	f.seek(entry_offset)
	self.write_cluster_entry(return_cluster)
	return return_cluster

	def write_file(self, head_cluster, start_byte, data):
	"""
	Write to a given FAT file.

	head_cluster: The first cluster in the file.
	start_byte: How many bytes in to the file to begin the write.
	data: The data to write.
	"""
	f = self.f
	last_offset = start_byte + len(data)
	current_offset = 0
	current_cluster = head_cluster

	while current_offset < last_offset:
	# Write everything that falls in the cluster starting at current_offset.
	data_begin = max(0, current_offset - start_byte)
	data_end = min(len(data),
	current_offset + self.bytes_per_cluster - start_byte)
	if data_end > data_begin:
	cluster_file_offset = (self.data_start() + self.root_entries * 32 +
	(current_cluster - 2) * self.bytes_per_cluster)
	f.seek(cluster_file_offset + max(0, start_byte - current_offset))
	f.write(data[data_begin:data_end])

	# Advance to the next cluster in the chain or get a new cluster if needed.
	current_offset += self.bytes_per_cluster
	if last_offset > current_offset:
	f.seek(FAT_TABLE_START + current_cluster * 2)
	next_cluster = read_le_short(f)
	if next_cluster > MAX_CLUSTER_ID:
	next_cluster = self.extend_cluster(current_cluster, len(data))
	current_cluster = next_cluster
	assert current_cluster > 0, "Cannot write free cluster"


	def add_item(directory, item):
	"""
	Copy a file into the given FAT directory. If the path given is a directory,
	copy recursively.
	directory: fat_dir to copy the file in to
	item: Path of local file to copy
	"""
	if os.path.isdir(item):
	base = os.path.basename(item)
	if len(base) == 0:
	base = os.path.basename(item[:-1])
	sub = directory.open_subdirectory(base)
	for next_item in sorted(os.listdir(item)):
	add_item(sub, os.path.join(item, next_item))
	else:
	with open(item, 'rb') as f:
	directory.new_file(os.path.basename(item), f)

	if __name__ == "__main__":
	if len(sys.argv) < 3:
	print("Usage: fat16copy.py <image> <file> [<file> ...]")
	print("Files are copied into the root of the image.")
	print("Directories are copied recursively")
	sys.exit(1)

	root = fat(sys.argv[1]).root

	for p in sys.argv[2:]:
	add_item(root, p)