@@ -16,7 +16,11 @@ internal sealed class FatChainEnumerator : IEnumerator<uint>
1616private uint index = uint . MaxValue ;
1717private uint current = uint . MaxValue ;
1818private long length = - 1 ;
19- private uint slow = uint . MaxValue ; // Floyd's cycle-finding algorithm
19+
20+ // Brent's cycle detection algorithm
21+ private uint cycleLength = 1 ;
22+ private uint power = 1 ;
23+ private uint slow = uint . MaxValue ;
2024
2125public FatChainEnumerator ( Fat fat , uint startSectorId )
2226{
@@ -64,7 +68,7 @@ public bool MoveNext()
6468index = 0 ;
6569current = startId ;
6670start = false ;
67- slow = startId ;
71+ slow = uint . MaxValue ;
6872return true ;
6973}
7074
@@ -87,15 +91,18 @@ public bool MoveNext()
8791throw new FileFormatException ( "FAT chain index is greater than the sector count." ) ;
8892}
8993
90- if ( index % 2 == 0 && ! SectorType . IsFreeOrEndOfChain ( slow ) )
94+ if ( value == slow )
95+ throw new FileFormatException ( "FAT chain contains a loop." ) ;
96+
97+ if ( cycleLength == power )
9198{
92- // Slow might become free or end of chain while shrinking
93- slow = fat [ slow ] ;
94- if ( slow == value )
95- throw new FileFormatException ( "FAT chain contains a loop." ) ;
99+ cycleLength = 0 ;
100+ power *= 2 ;
101+ slow = value ;
96102}
97103
98104current = value ;
105+ cycleLength ++ ;
99106return true ;
100107}
101108
@@ -242,6 +249,8 @@ public void Reset(uint startSectorId)
242249index = uint . MaxValue ;
243250current = uint . MaxValue ;
244251slow = uint . MaxValue ;
252+ cycleLength = 1 ;
253+ power = 1 ;
245254}
246255
247256[ ExcludeFromCodeCoverage ]