tools/mkfat.py

   1 #!/usr/bin/env python
   2 #
   3 # Copyright (c) 2008 Martin Decky
   4 # All rights reserved.
   5 #
   6 # Redistribution and use in source and binary forms, with or without
   7 # modification, are permitted provided that the following conditions
   8 # are met:
   9 #
  10 # - Redistributions of source code must retain the above copyright
  11 #   notice, this list of conditions and the following disclaimer.
  12 # - Redistributions in binary form must reproduce the above copyright
  13 #   notice, this list of conditions and the following disclaimer in the
  14 #   documentation and/or other materials provided with the distribution.
  15 # - The name of the author may not be used to endorse or promote products
  16 #   derived from this software without specific prior written permission.
  17 #
  18 # THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19 # IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20 # OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21 # IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22 # INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23 # NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24 # DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25 # THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26 # (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27 # THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28 #
  29
  30 """
  31 FAT creator
  32 """
  33
  34 import sys
  35 import os
  36 import random
  37 import xstruct
  38 import array
  39 from imgutil import *
  40
  41 def subtree_size(root, cluster_size, dirent_size):
  42         "Recursive directory walk and calculate size"
  43
  44         size = 0
  45         files = 2
  46
  47         for item in listdir_items(root):
  48                 if item.is_file:
  49                         size += align_up(item.size, cluster_size)
  50                         files += 1
  51                 elif item.is_dir:
  52                         size += subtree_size(item.path, cluster_size, dirent_size)
  53                         files += 1
  54
  55         return size + align_up(files * dirent_size, cluster_size)
  56
  57 def root_entries(root):
  58         "Return number of root directory entries"
  59
  60         return len(os.listdir(root))
  61
  62 def write_file(item, outf, cluster_size, data_start, fat, reserved_clusters):
  63         "Store the contents of a file"
  64
  65         prev = -1
  66         first = 0
  67
  68         for data in chunks(item, cluster_size):
  69                 empty_cluster = fat.index(0)
  70                 fat[empty_cluster] = 0xffff
  71
  72                 if (prev != -1):
  73                         fat[prev] = empty_cluster
  74                 else:
  75                         first = empty_cluster
  76
  77                 prev = empty_cluster
  78
  79                 outf.seek(data_start + (empty_cluster - reserved_clusters) * cluster_size)
  80                 outf.write(data)
  81
  82         return first, item.size
  83
  84 def write_directory(directory, outf, cluster_size, data_start, fat, reserved_clusters, dirent_size, empty_cluster):
  85         "Store the contents of a directory"
  86
  87         length = len(directory)
  88         size = length * dirent_size
  89         prev = -1
  90         first = 0
  91
  92         i = 0
  93         rd = 0;
  94         while (rd < size):
  95                 if (prev != -1):
  96                         empty_cluster = fat.index(0)
  97                         fat[empty_cluster] = 0xffff
  98                         fat[prev] = empty_cluster
  99                 else:
 100                         first = empty_cluster
 101
 102                 prev = empty_cluster
 103
 104                 data = bytes()
 105                 data_len = 0
 106                 while ((i < length) and (data_len < cluster_size)):
 107                         if (i == 0):
 108                                 directory[i].cluster = empty_cluster
 109
 110                         data += directory[i].pack()
 111                         data_len += dirent_size
 112                         i += 1
 113
 114                 outf.seek(data_start + (empty_cluster - reserved_clusters) * cluster_size)
 115                 outf.write(data)
 116                 rd += len(data)
 117
 118         return first, size
 119
 120 DIR_ENTRY = """little:
 121         char name[8]               /* file name */
 122         char ext[3]                /* file extension */
 123         uint8_t attr               /* file attributes */
 124         uint8_t lcase              /* file name case (NT extension) */
 125         uint8_t ctime_fine         /* create time (fine resolution) */
 126         uint16_t ctime             /* create time */
 127         uint16_t cdate             /* create date */
 128         uint16_t adate             /* access date */
 129         padding[2]                 /* EA-index */
 130         uint16_t mtime             /* modification time */
 131         uint16_t mdate             /* modification date */
 132         uint16_t cluster           /* first cluster */
 133         uint32_t size              /* file size */
 134 """
 135
 136 DOT_DIR_ENTRY = """little:
 137         uint8_t signature          /* 0x2e signature */
 138         char name[7]               /* empty */
 139         char ext[3]                /* empty */
 140         uint8_t attr               /* file attributes */
 141         padding[1]                 /* reserved for NT */
 142         uint8_t ctime_fine         /* create time (fine resolution) */
 143         uint16_t ctime             /* create time */
 144         uint16_t cdate             /* create date */
 145         uint16_t adate             /* access date */
 146         padding[2]                 /* EA-index */
 147         uint16_t mtime             /* modification time */
 148         uint16_t mdate             /* modification date */
 149         uint16_t cluster           /* first cluster */
 150         uint32_t size              /* file size */
 151 """
 152
 153 DOTDOT_DIR_ENTRY = """little:
 154         uint8_t signature[2]       /* 0x2e signature */
 155         char name[6]               /* empty */
 156         char ext[3]                /* empty */
 157         uint8_t attr               /* file attributes */
 158         padding[1]                 /* reserved for NT */
 159         uint8_t ctime_fine         /* create time (fine resolution) */
 160         uint16_t ctime             /* create time */
 161         uint16_t cdate             /* create date */
 162         uint16_t adate             /* access date */
 163         padding[2]                 /* EA-index */
 164         uint16_t mtime             /* modification time */
 165         uint16_t mdate             /* modification date */
 166         uint16_t cluster           /* first cluster */
 167         uint32_t size              /* file size */
 168 """
 169
 170 LFN_DIR_ENTRY = """little:
 171         uint8_t seq                /* sequence number */
 172         char name1[10]             /* first part of the name */
 173         uint8_t attr               /* attributes */
 174         uint8_t rec_type           /* LFN record type */
 175         uint8_t checksum           /* LFN checksum */
 176         char name2[12]             /* second part of the name */
 177         uint16_t cluster           /* cluster */
 178         char name3[4]              /* third part of the name */
 179 """
 180
 181 lchars = set(['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J',
 182               'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T',
 183               'U', 'V', 'W', 'X', 'Y', 'Z',
 184               '0', '1', '2', '3', '4', '5', '6', '7', '8', '9',
 185               '!', '#', '$', '%', '&', '\'', '(', ')', '-', '@',
 186               '^', '_', '`', '{', '}', '~', '.'])
 187
 188 def fat_lchars(name):
 189         "Filter FAT legal characters"
 190
 191         filtered_name = b''
 192         filtered = False
 193
 194         for char in name.encode('ascii', 'replace').upper():
 195                 if char in lchars:
 196                         filtered_name += char
 197                 else:
 198                         filtered_name += b'_'
 199                         filtered = True
 200
 201         return (filtered_name, filtered)
 202
 203 def fat_name83(name, name83_list):
 204         "Create a 8.3 name for the given name"
 205
 206         ascii_name, lfn = fat_lchars(name)
 207         # Splitting works only on strings, not on bytes
 208         ascii_parts = ascii_name.decode('utf8').split('.')
 209
 210         short_name = ''
 211         short_ext = ''
 212
 213         if len(ascii_name) > 11:
 214                 lfn = True
 215
 216         if len(ascii_parts) > 0:
 217                 short_name = ascii_parts[0]
 218                 if len(short_name) > 8:
 219                         lfn = True
 220
 221         if len(ascii_parts) > 1:
 222                 short_ext = ascii_parts[-1]
 223                 if len(short_ext) > 3:
 224                         lfn = True
 225
 226         if len(ascii_parts) > 2:
 227                 lfn = True
 228
 229         if lfn == False:
 230                 name83_list.append(short_name + '.' + short_ext)
 231                 return (short_name.ljust(8)[0:8], short_ext.ljust(3)[0:3], False)
 232
 233         # For filenames with multiple extensions, we treat the last one
 234         # as the actual extension. The rest of the filename is stripped
 235         # of dots and concatenated to form the short name
 236         for part in ascii_parts[1:-1]:
 237                 short_name += part
 238
 239         for number in range(1, 999999):
 240                 number_str = ('~' + str(number)).upper()
 241
 242                 if len(short_name) + len(number_str) > 8:
 243                         short_name = short_name[0:8 - len(number_str)]
 244
 245                 short_name += number_str;
 246
 247                 if not (short_name + '.' + short_ext) in name83_list:
 248                         break
 249
 250         name83_list.append(short_name + '.' + short_ext)
 251         return (short_name.ljust(8)[0:8], short_ext.ljust(3)[0:3], True)
 252
 253 def create_lfn_dirent(name, seq, checksum):
 254         "Create LFN directory entry"
 255
 256         entry = xstruct.create(LFN_DIR_ENTRY)
 257         name_rest = name[26:]
 258
 259         if len(name_rest) > 0:
 260                 entry.seq = seq
 261         else:
 262                 entry.seq = seq | 0x40
 263
 264         entry.name1 = name[0:10]
 265         entry.name2 = name[10:22]
 266         entry.name3 = name[22:26]
 267
 268         entry.attr = 0x0F
 269         entry.rec_type = 0
 270         entry.checksum = checksum
 271         entry.cluster = 0
 272
 273         return (entry, name_rest)
 274
 275 def lfn_checksum(name):
 276         "Calculate LFN checksum"
 277
 278         checksum = 0
 279         for i in range(0, 11):
 280                 checksum = (((checksum & 1) << 7) + (checksum >> 1) + ord(name[i])) & 0xFF
 281
 282         return checksum
 283
 284 def create_dirent(name, name83_list, directory, cluster, size):
 285         short_name, short_ext, lfn = fat_name83(name, name83_list)
 286
 287         dir_entry = xstruct.create(DIR_ENTRY)
 288
 289         dir_entry.name = short_name
 290         dir_entry.ext = short_ext
 291
 292         if (directory):
 293                 dir_entry.attr = 0x30
 294         else:
 295                 dir_entry.attr = 0x20
 296
 297         dir_entry.lcase = 0x18
 298         dir_entry.ctime_fine = 0 # FIXME
 299         dir_entry.ctime = 0 # FIXME
 300         dir_entry.cdate = 0 # FIXME
 301         dir_entry.adate = 0 # FIXME
 302         dir_entry.mtime = 0 # FIXME
 303         dir_entry.mdate = 0 # FIXME
 304         dir_entry.cluster = cluster
 305
 306         if (directory):
 307                 dir_entry.size = 0
 308         else:
 309                 dir_entry.size = size
 310
 311         if not lfn:
 312                 return [dir_entry]
 313
 314         long_name = name.encode('utf_16_le')
 315         entries = [dir_entry]
 316
 317         seq = 1
 318         checksum = lfn_checksum(dir_entry.name + dir_entry.ext)
 319
 320         while len(long_name) > 0:
 321                 long_entry, long_name = create_lfn_dirent(long_name, seq, checksum)
 322                 entries.append(long_entry)
 323                 seq += 1
 324
 325         entries.reverse()
 326         return entries
 327
 328 def create_dot_dirent(empty_cluster):
 329         dir_entry = xstruct.create(DOT_DIR_ENTRY)
 330
 331         dir_entry.signature = 0x2e
 332         dir_entry.name = b'       '
 333         dir_entry.ext = b'   '
 334         dir_entry.attr = 0x10
 335
 336         dir_entry.ctime_fine = 0 # FIXME
 337         dir_entry.ctime = 0 # FIXME
 338         dir_entry.cdate = 0 # FIXME
 339         dir_entry.adate = 0 # FIXME
 340         dir_entry.mtime = 0 # FIXME
 341         dir_entry.mdate = 0 # FIXME
 342         dir_entry.cluster = empty_cluster
 343         dir_entry.size = 0
 344
 345         return dir_entry
 346
 347 def create_dotdot_dirent(parent_cluster):
 348         dir_entry = xstruct.create(DOTDOT_DIR_ENTRY)
 349
 350         dir_entry.signature = [0x2e, 0x2e]
 351         dir_entry.name = b'      '
 352         dir_entry.ext = b'   '
 353         dir_entry.attr = 0x10
 354
 355         dir_entry.ctime_fine = 0 # FIXME
 356         dir_entry.ctime = 0 # FIXME
 357         dir_entry.cdate = 0 # FIXME
 358         dir_entry.adate = 0 # FIXME
 359         dir_entry.mtime = 0 # FIXME
 360         dir_entry.mdate = 0 # FIXME
 361         dir_entry.cluster = parent_cluster
 362         dir_entry.size = 0
 363
 364         return dir_entry
 365
 366 def recursion(head, root, outf, cluster_size, root_start, data_start, fat, reserved_clusters, dirent_size, parent_cluster):
 367         "Recursive directory walk"
 368
 369         directory = []
 370         name83_list = []
 371
 372         if not head:
 373                 # Directory cluster preallocation
 374                 empty_cluster = fat.index(0)
 375                 fat[empty_cluster] = 0xFFFF
 376
 377                 directory.append(create_dot_dirent(empty_cluster))
 378                 directory.append(create_dotdot_dirent(parent_cluster))
 379         else:
 380                 empty_cluster = 0
 381
 382         for item in listdir_items(root):
 383                 if item.is_file:
 384                         rv = write_file(item, outf, cluster_size, data_start, fat, reserved_clusters)
 385                         directory.extend(create_dirent(item.name, name83_list, False, rv[0], rv[1]))
 386                 elif item.is_dir:
 387                         rv = recursion(False, item.path, outf, cluster_size, root_start, data_start, fat, reserved_clusters, dirent_size, empty_cluster)
 388                         directory.extend(create_dirent(item.name, name83_list, True, rv[0], rv[1]))
 389
 390         if head:
 391                 outf.seek(root_start)
 392                 for dir_entry in directory:
 393                         outf.write(dir_entry.pack())
 394         else:
 395                 return write_directory(directory, outf, cluster_size, data_start, fat, reserved_clusters, dirent_size, empty_cluster)
 396
 397 BOOT_SECTOR = """little:
 398         uint8_t jmp[3]             /* jump instruction */
 399         char oem[8]                /* OEM string */
 400         uint16_t sector            /* bytes per sector */
 401         uint8_t cluster            /* sectors per cluster */
 402         uint16_t reserved          /* reserved sectors */
 403         uint8_t fats               /* number of FATs */
 404         uint16_t rootdir           /* root directory entries */
 405         uint16_t sectors           /* total number of sectors */
 406         uint8_t descriptor         /* media descriptor */
 407         uint16_t fat_sectors       /* sectors per single FAT */
 408         uint16_t track_sectors     /* sectors per track */
 409         uint16_t heads             /* number of heads */
 410         uint32_t hidden            /* hidden sectors */
 411         uint32_t sectors_big       /* total number of sectors (if sectors == 0) */
 412
 413         /* Extended BIOS Parameter Block */
 414         uint8_t drive              /* physical drive number */
 415         padding[1]                 /* reserved (current head) */
 416         uint8_t extboot_signature  /* extended boot signature */
 417         uint32_t serial            /* serial number */
 418         char label[11]             /* volume label */
 419         char fstype[8]             /* filesystem type */
 420         padding[448]               /* boot code */
 421         uint8_t boot_signature[2]  /* boot signature */
 422 """
 423
 424 EMPTY_SECTOR = """little:
 425         padding[512]               /* empty sector data */
 426 """
 427
 428 FAT_ENTRY = """little:
 429         uint16_t next              /* FAT16 entry */
 430 """
 431
 432 def usage(prname):
 433         "Print usage syntax"
 434         print(prname + " <EXTRA_BYTES> <PATH> <IMAGE>")
 435
 436 def main():
 437         if (len(sys.argv) < 4):
 438                 usage(sys.argv[0])
 439                 return
 440
 441         if (not sys.argv[1].isdigit()):
 442                 print("<EXTRA_BYTES> must be a number")
 443                 return
 444
 445         extra_bytes = int(sys.argv[1])
 446
 447         path = os.path.abspath(sys.argv[2])
 448         if (not os.path.isdir(path)):
 449                 print("<PATH> must be a directory")
 450                 return
 451
 452         fat16_clusters = 4096
 453
 454         sector_size = 512
 455         cluster_size = 4096
 456         dirent_size = 32
 457         fatent_size = 2
 458         fat_count = 2
 459         reserved_clusters = 2
 460
 461         # Make sure the filesystem is large enough for FAT16
 462         size = subtree_size(path, cluster_size, dirent_size) + reserved_clusters * cluster_size + extra_bytes
 463         while (size // cluster_size < fat16_clusters):
 464                 if (cluster_size > sector_size):
 465                         cluster_size = cluster_size // 2
 466                         size = subtree_size(path, cluster_size, dirent_size) + reserved_clusters * cluster_size + extra_bytes
 467                 else:
 468                         size = fat16_clusters * cluster_size + reserved_clusters * cluster_size
 469
 470         root_size = align_up(root_entries(path) * dirent_size, cluster_size)
 471
 472         fat_size = align_up(align_up(size, cluster_size) // cluster_size * fatent_size, sector_size)
 473
 474         sectors = (cluster_size + fat_count * fat_size + root_size + size) // sector_size
 475         root_start = cluster_size + fat_count * fat_size
 476         data_start = root_start + root_size
 477
 478         outf = open(sys.argv[3], "wb")
 479
 480         boot_sector = xstruct.create(BOOT_SECTOR)
 481         boot_sector.jmp = [0xEB, 0x3C, 0x90]
 482         boot_sector.oem = b'MSDOS5.0'
 483         boot_sector.sector = sector_size
 484         boot_sector.cluster = cluster_size // sector_size
 485         boot_sector.reserved = cluster_size // sector_size
 486         boot_sector.fats = fat_count
 487         boot_sector.rootdir = root_size // dirent_size
 488         if (sectors <= 65535):
 489                 boot_sector.sectors = sectors
 490         else:
 491                 boot_sector.sectors = 0
 492         boot_sector.descriptor = 0xF8
 493         boot_sector.fat_sectors = fat_size // sector_size
 494         boot_sector.track_sectors = 63
 495         boot_sector.heads = 6
 496         boot_sector.hidden = 0
 497         if (sectors > 65535):
 498                 boot_sector.sectors_big = sectors
 499         else:
 500                 boot_sector.sectors_big = 0
 501
 502         boot_sector.drive = 0x80
 503         boot_sector.extboot_signature = 0x29
 504         boot_sector.serial = random.randint(0, 0x7fffffff)
 505         boot_sector.label = b'HELENOS'
 506         boot_sector.fstype = b'FAT16   '
 507         boot_sector.boot_signature = [0x55, 0xAA]
 508
 509         outf.write(boot_sector.pack())
 510
 511         empty_sector = xstruct.create(EMPTY_SECTOR)
 512
 513         # Reserved sectors
 514         for i in range(1, cluster_size // sector_size):
 515                 outf.write(empty_sector.pack())
 516
 517         # FAT tables
 518         for i in range(0, fat_count):
 519                 for j in range(0, fat_size // sector_size):
 520                         outf.write(empty_sector.pack())
 521
 522         # Root directory
 523         for i in range(0, root_size // sector_size):
 524                 outf.write(empty_sector.pack())
 525
 526         # Data
 527         for i in range(0, size // sector_size):
 528                 outf.write(empty_sector.pack())
 529
 530         fat = array.array('L', [0] * (fat_size // fatent_size))
 531         fat[0] = 0xfff8
 532         fat[1] = 0xffff
 533
 534         recursion(True, path, outf, cluster_size, root_start, data_start, fat, reserved_clusters, dirent_size, 0)
 535
 536         # Store FAT
 537         fat_entry = xstruct.create(FAT_ENTRY)
 538         for i in range(0, fat_count):
 539                 outf.seek(cluster_size + i * fat_size)
 540                 for j in range(0, fat_size // fatent_size):
 541                         fat_entry.next = fat[j]
 542                         outf.write(fat_entry.pack())
 543
 544         outf.close()
 545
 546 if __name__ == '__main__':
 547         main()