File Coverage

blib/lib/Sys/Export/VFAT/Geometry.pm

Criterion	Covered	Total	%
statement	245	288	85.0
branch	52	98	53.0
condition	39	85	45.8
subroutine	44	49	89.8
pod	40	40	100.0
total	420	560	75.0

package Sys::Export::VFAT::Geometry;

# ABSTRACT: Calculate addresses and sizes of structures within a FAT filesystem
our $VERSION = '0.006'; # VERSION


use v5.28;
use warnings;
use experimental qw( signatures );
use Sys::Export qw( isa_hash isa_int isa_pow2 round_up_to_pow2 round_up_to_multiple );
use Scalar::Util qw( dualvar );
use POSIX 'ceil';
use Carp;
our @CARP_NOT= qw( Sys::Export::VFAT );
use constant {
   FAT12 => dualvar(12, "FAT12"),
   FAT16 => dualvar(16, "FAT16"),
   FAT32 => dualvar(32, "FAT32"),
   FAT12_MAX_CLUSTERS       => 4085-1,
   FAT12_IDEAL_MAX_CLUSTERS => 4085-16,   # docs recommend 16 away from cutoff on either side
   FAT16_MIN_CLUSTERS       => 4085,
   FAT16_IDEAL_MIN_CLUSTERS => 4085+16,
   FAT16_MAX_CLUSTERS       => 65525-1,
   FAT16_IDEAL_MAX_CLUSTERS => 65525-16,
   FAT32_MIN_CLUSTERS       => 65525,
   FAT32_IDEAL_MIN_CLUSTERS => 65525+16,
   FAT32_MAX_CLUSTERS       => 0xFFFFFF5, # can't allow 0xFFFFFF7 to be allocatable ID
};
use Exporter 'import';
our @EXPORT_OK= qw( FAT12 FAT16 FAT32 FAT12_MAX_CLUSTERS FAT12_IDEAL_MAX_CLUSTERS
   FAT16_MIN_CLUSTERS FAT16_IDEAL_MIN_CLUSTERS FAT16_MAX_CLUSTERS FAT16_IDEAL_MAX_CLUSTERS
   FAT32_MIN_CLUSTERS FAT32_IDEAL_MIN_CLUSTERS FAT32_MAX_CLUSTERS );


sub new($class, @attrs) {
   my %attrs= @attrs == 1 && isa_hash $attrs[0]? %{$attrs[0]} : @attrs;
   my ($bytes_per_sector, $sectors_per_cluster,   $fat_count,     $reserved_sector_count,
       $fat_sector_count, $root_dirent_count,     $cluster_count, $total_sector_count,
       $min_bits,         $volume_offset,         $align_clusters
      ) = delete @attrs{qw(
        bytes_per_sector   sectors_per_cluster     fat_count       reserved_sector_count
        fat_sector_count   root_dirent_count       cluster_count   total_sector_count
        min_bits           volume_offset           align_clusters
      )};
   !defined $align_clusters or isa_pow2($align_clusters)
      or croak "align_clusters must be a power of 2 (was $align_clusters)";
   $volume_offset //= 0;
   isa_int($volume_offset) && $volume_offset >= 0
      or croak "volume_offset must be a non-negative integer";

   $bytes_per_sector //= 512;
   isa_pow2($bytes_per_sector) && 512 <= $bytes_per_sector && $bytes_per_sector <= 4096
      or croak "Invalid bytes_per_sector $bytes_per_sector";

   # Default sectors_per_cluster to whatever makes 4K
   $sectors_per_cluster //= ($bytes_per_sector >= 4096? 1 : 4096 / $bytes_per_sector);
   isa_pow2($sectors_per_cluster) && $sectors_per_cluster <= 128
      or croak "Invalid sectors_per_cluster $sectors_per_cluster";
   my $cluster_size= $bytes_per_sector * $sectors_per_cluster;
   $cluster_size <= 32*1024
      or carp "Warning: bytes_per_sector * sectors_per_cluster > 32KiB which is not valid for some drivers";

   # Default fat_count to 2 unless specified otherwise
   $fat_count //= 2;
   isa_int $fat_count && 0 < $fat_count && $fat_count <= 255
      or croak "Invalid fat_count $fat_count";

   my $self= bless {
      bytes_per_sector      => $bytes_per_sector,
      sectors_per_cluster   => $sectors_per_cluster,
      fat_count             => $fat_count,
      volume_offset         => $volume_offset,
   };

   # From here down, we are either determining cluster_count from other properties,
   # or deriving other properties from cluster_count.
   my $bits;
   if (defined $reserved_sector_count && defined $fat_sector_count
    && defined $root_dirent_count && defined $total_sector_count
   ) {
      # All main properties of the geometry are defined.
      my $root_sector_count= int(($root_dirent_count + ($self->dirent_per_sector-1)) / $self->dirent_per_sector);
      my $data_sectors= $total_sector_count - $reserved_sector_count - $fat_count * $fat_sector_count - $root_sector_count;
      my $calc_cluster_count= int($data_sectors / $sectors_per_cluster);
      croak "Supplied cluster_count disagrees with computed value"
         if defined $cluster_count && $cluster_count != $calc_cluster_count;
      $cluster_count //= $calc_cluster_count;
      $bits= $cluster_count < FAT16_MIN_CLUSTERS? FAT12
           : $cluster_count < FAT32_MIN_CLUSTERS? FAT16
           : FAT32;
   }
   elsif (defined $cluster_count) {
      isa_int $cluster_count && $cluster_count > 0
         or croak "Invalid cluster_count '$cluster_count'";
      # FAT docs recommend avoiding numbers near the boundary of FAT12/FAT16/FAT32 to avoid
      # other people's math errors.  But, allow the caller to disable this adjustment.
      unless (delete $attrs{exact_cluster_count}) {
         if ($cluster_count >= FAT12_IDEAL_MAX_CLUSTERS && $cluster_count < FAT16_IDEAL_MIN_CLUSTERS) {
            $cluster_count= FAT16_IDEAL_MIN_CLUSTERS;
         } elsif ($cluster_count >= FAT16_IDEAL_MAX_CLUSTERS && $cluster_count < FAT32_IDEAL_MIN_CLUSTERS) {
            $cluster_count= FAT32_IDEAL_MIN_CLUSTERS;
         }
      }
      # These are the official boundary numbers that determine the filesystem type
      $min_bits //= FAT12;
      $bits= $cluster_count < FAT16_MIN_CLUSTERS? FAT12
              : $cluster_count < FAT32_MIN_CLUSTERS? FAT16
              : FAT32;
      if ($bits < $min_bits) {
         $bits= $min_bits;
         # Increase to the minimum number of clusters if a specific number of bits
         # was requested.
         $cluster_count= ($bits == FAT16)? FAT16_IDEAL_MIN_CLUSTERS : FAT32_IDEAL_MIN_CLUSTERS;
      }
   }
   else {
      croak "Not enough attributes supplied to determine geometry";
   }
   $self->{cluster_count}= $cluster_count;
   $self->{bits}= $bits;

   # Check how many sectors are occupied by each allocation table
   my $fat_byte_count= ( ($cluster_count + 2) * $bits + 7 ) >> 3; # round up to bytes
   if (defined $fat_sector_count) {
      $fat_sector_count * $bytes_per_sector >= $fat_byte_count
         or croak "Invalid fat_sector_count, smaller than $fat_byte_count bytes";
   } else {
      $fat_sector_count= int(($fat_byte_count + ($bytes_per_sector - 1)) / $bytes_per_sector);
   }
   $self->{fat_sector_count}= $fat_sector_count;

   # Check how many sectors are occupied by root directory entries
   # For fat12/16, The FAT spec document suggests 512 as a good default
   # Allow the user to supply the actual number of root entries and then we round that.
   my $used_root_dirent_count= delete $attrs{used_root_dirent_count};
   if ($bits < FAT32) {
      if (defined $root_dirent_count) {
         $root_dirent_count >= 1 && $root_dirent_count < 0xFFFF
            or croak "Invalid root_dirent_count for FAT12/16";
      } else {
         $root_dirent_count= $used_root_dirent_count // 512;
         # Round up to as many as fit in this number of sectors
         my $remainder= ($root_dirent_count & ($self->dirent_per_sector - 1));
         $root_dirent_count += ($self->dirent_per_sector - $remainder)
            if $remainder;
      }

      ($reserved_sector_count //= 1) == 1
         or croak "reserved_sector_count should be 1 for FAT12/16";
   } else {
      ($root_dirent_count //= 0) == 0
         or croak "root_dirent_count must be zero for FAT32";

      $reserved_sector_count //= 32;
      isa_int $reserved_sector_count && $reserved_sector_count >= 2
         or croak "reserved_sector_count must be greater than 2 for FAT32";
   }

   # If caller requested alignment of clusters, figure that out
   if (defined $align_clusters && $align_clusters > $bytes_per_sector) {
      # there's a method for this, but avoid caching things yet
      my $data_addr= $volume_offset + $bytes_per_sector * (
         $reserved_sector_count
         + ($fat_count*$fat_sector_count)
         + ceil($root_dirent_count / $self->dirent_per_sector)
      );
      # If the cluster size is greater or equal to the requested alignment, ensure the
      # data start falls on that boundary.
      # If the cluster size is smaller than the requested alignment, ensure the data start
      # falls on a cluster boundary so that some number of clusters will equal the alignment.
      my $align= ($cluster_size >= $align_clusters)? $align_clusters : $cluster_size;
      if (my $ofs= $data_addr & ($align-1)) {
         my $shift_n_sectors= ($align - $ofs) / $bytes_per_sector;
         #say sprintf "# remainder=0x%X, cluster_size=$cluster_size align_clusters=$align_clusters $align-$ofs=".($align-$ofs)." shift %d sectors", $ofs, $shift_n_sectors;
         if ($bits < FAT32) {
            # Reserved sectors should be 1, so expand number of root entries
            $root_dirent_count += $shift_n_sectors * $self->dirent_per_sector;
         } else {
            # Add however many reserved sectors we need
            $reserved_sector_count += $shift_n_sectors;
         }
      }
   }
   $self->{root_dirent_count}= $root_dirent_count;
   $self->{reserved_sector_count}= $reserved_sector_count;

   carp "Unused constructor parameters: ".join(' ', keys %attrs)
      if keys %attrs;
   $self;
}


sub volume_offset($self)  { $self->{volume_offset} }

sub bytes_per_sector($self)    { $self->{bytes_per_sector} }
sub sectors_per_cluster($self) { $self->{sectors_per_cluster} }
sub bytes_per_cluster($self)   { $self->{bytes_per_sector} * $self->{sectors_per_cluster} }
sub dirent_per_sector($self)   { $self->{bytes_per_sector} / 32 }
sub dirent_per_cluster($self)  { $self->{bytes_per_sector} * $self->{sectors_per_cluster} / 32 }


sub bits($self)                  { $self->{bits} }
sub reserved_sector_count($self) { $self->{reserved_sector_count} }
sub reserved_size($self)         { $self->{reserved_sector_count} * $self->bytes_per_sector }
sub fat_count($self)             { $self->{fat_count} }
sub fat_sector_count($self)      { $self->{fat_sector_count} }
sub fat_size($self)              { $self->{fat_sector_count} * $self->bytes_per_sector }
sub cluster_count($self)         { $self->{cluster_count} }
sub min_cluster_id($self)        { 2 }
sub max_cluster_id($self)        { $self->cluster_count + 1 }
sub root_dirent_count($self)     { $self->{root_dirent_count} }
sub root_dir_sector_count($self) { ceil($self->root_dirent_count / $self->dirent_per_sector) }
sub root_dir_size($self)         { $self->root_dir_sector_count * $self->bytes_per_sector }

sub root_dir_start_sector($self) {
   $self->reserved_sector_count + $self->fat_count * $self->fat_sector_count
}
sub root_dir_offset($self) { $self->root_dir_start_sector * $self->bytes_per_sector }
sub data_start_sector($self) {
   $self->{data_start_sector} //= $self->root_dir_start_sector + $self->root_dir_sector_count;
}
sub data_limit_sector($self) {
   $self->data_start_sector + $self->cluster_count * $self->sectors_per_cluster
}
sub data_start_offset($self) { $self->data_start_sector * $self->bytes_per_sector }
sub data_limit_offset($self) { $self->data_limit_sector * $self->bytes_per_sector }
sub data_start_device_offset($self) { $self->volume_offset + $self->data_start_offset }
sub data_limit_device_offset($self) { $self->volume_offset + $self->data_limit_offset }

sub data_sector_count($self) {
   $self->total_sector_count - $self->data_start_sector;
}

sub total_sector_count($self) {
   $self->{total_sector_count} //= $self->data_start_sector
      + $self->cluster_count * $self->sectors_per_cluster;
}
sub total_size($self) { $self->total_sector_count * $self->bytes_per_sector }


sub get_cluster_start_sector($self, $cluster_id) {
   croak "Cluster 0 and 1 are reserved" if $cluster_id < 2;
   croak "Cluster $cluster_id beyond end of volume" if $cluster_id > $self->max_cluster_id;
   return $self->data_start_sector + ($cluster_id-2) * $self->sectors_per_cluster;
}
sub get_cluster_offset($self, $cluster_id) {
   $self->get_cluster_start_sector($cluster_id) * $self->bytes_per_sector;
}
sub get_cluster_device_offset($self, $cluster_id) {
   $self->volume_offset + $self->get_cluster_offset($cluster_id);
}

sub get_cluster_of_sector($self, $sector_idx) {
   return undef if $sector_idx < $self->data_start_sector;
   my $cluster= int(($sector_idx - $self->data_start_sector) / $self->sectors_per_cluster);
   return undef if $cluster >= $self->cluster_count;
   return $cluster + 2;
}
sub get_cluster_of_offset($self, $offset) {
   $self->get_cluster_of_sector(int($offset / $self->bytes_per_sector));
}
sub get_cluster_of_device_offset($self, $addr) {
   $self->get_cluster_of_offset($addr - $self->volume_offset);
}


sub get_cluster_extent_of_volume_extent($self, $offset, $size) {
   my $cl_start= $self->get_cluster_of_offset($offset);
   $cl_start
      or croak "Offset $offset falls outside of cluster data region";
   $self->get_cluster_offset($cl_start) == $offset
      or croak "FAT_offset not aligned to a cluster boundary";
   my $cl_cnt= ceil($size / $self->bytes_per_cluster);
   $cl_start + $cl_cnt <= $self->max_cluster_id+1
      or croak "byte range ($offset, $size) exceeds final cluster of volume";
   return ($cl_start, $cl_cnt);
}


sub get_cluster_extent_of_device_extent($self, $addr, $size) {
   $self->get_cluster_extent_of_volume_extent($addr - $self->volume_offset, $size);
}


sub get_cluster_alignment_of_device_alignment($self, $align) {
   my $cluster_size= $self->bytes_per_cluster;
   # If the cluster size is greater or equal to the requested alignment, verify that the
   # data start (plus the volume offset that was implicitly added to every volume address)
   # meets that alignment.  If so, every cluster is aligned and the return value is (1,0)
   if ($cluster_size >= $align) {
      croak "Clusters are not aligned to $align"
         if $self->data_start_device_offset & ($align-1);
      return (1,0);
   }
   # Otherwise, make sure the data_start (plus implied volume offset) is aligned to
   # cluster_size, so then some multiple of clusters will reach the requested alignment.
   croak "Clusters are not aligned to $cluster_size"
      if $self->data_start_device_offset & ($cluster_size-1);
   # The cluster alignment will be whatever multiple of clusters equals the byte alignment.
   # This will be at least 2.
   my $cl_align= $align / $cluster_size;
   # How many bytes away from alignment is the beginning of ficticious cluster 0?
   my $ofs_of_cl0= ($self->data_start_device_offset - ($cluster_size*2)) & ($align-1);
   # If not aligned, add the rest of the distance to the next alignment.
   my $cl_ofs= !$ofs_of_cl0? 0 : ($align - $ofs_of_cl0) / $cluster_size;
   return ($cl_align, $cl_ofs);
}


sub unpack {
   my $class= shift;
   my $buf_ref= ref $_[0] eq 'SCALAR'? $_[0] : \$_[0];
   my %attrs= ref $_[1] eq 'HASH'? %{$_[1]} : @_[1..$#_];
   length($$buf_ref) >= 512 or croak "Pass at least the entire first sector to 'unpack'";
   # According to the official spec, the only way to know whether you have FAT32 or FAT16
   # is to calculate the count of clusters available in the data region, which this module
   # implements in the constructor.  However, in order to unpack all of the fields of
   # sector0, you have to know whether it is FAT16 or FAT32 because FAT32 moves some of the
   # fields.  But you need those extended fields to calculate whether it is FAT32 or not...
   # It's sort of a bullshit circular dependency when clearly you could use the
   # BPB_RootEntCnt to know whether it was FAT32 or not, since FAT32 will *always* be 0 and
   # the previous generations *can't* be 0.
   # Anyway, instead of uniform single-pass field unpacking, we get this:
   state %fields= qw(
      bytes_per_sector      @11v
      sectors_per_cluster   @13C
      reserved_sector_count @14v
      fat_count             @16C
      root_dirent_count     @17v
      fat_sector_count      @22v
      fat_sector_count32    @36V
      total_sector_count    @19v
      total_sector_count32  @32V
   );
   state @fields= keys %fields;
   state $packstr= join ' ', values %fields;

   @attrs{@fields}= unpack $packstr, $$buf_ref;
   for (qw( fat_sector_count total_sector_count )) {
      my $_32= delete $attrs{$_.'32'};
      $attrs{$_} ||= $_32;
   }
   return $class->new(%attrs);
}

# Avoiding dependency on namespace::clean
delete @{Sys::Export::VFAT::Geometry::}{qw(
   carp confess croak ceil dualvar
   isa_hash isa_int isa_pow2 round_up_to_multiple round_up_to_pow2
)};
1;

__END__