Dave Jarvis' Repositories

<?php
require_once __DIR__ . '/StreamReader.php';
require_once __DIR__ . '/PackStreamManager.php';

class PackIndex {
  private string $indexFile;
  private string $packFile;
  private array  $fanoutCache;
  private string $buffer;
  private int    $bufferOffset;

  public function __construct( string $indexFile ) {
    $this->indexFile    = $indexFile;
    $this->packFile     = str_replace( '.idx', '.pack', $indexFile );
    $this->fanoutCache  = [];
    $this->buffer       = '';
    $this->bufferOffset = -1;
  }

  public function search(
    PackStreamManager $manager,
    string $sha,
    callable $onFound
  ): void {
    $manager->computeInt(
      $this->indexFile,
      function( StreamReader $stream ) use ( $sha, $onFound ): int {
        $this->ensureFanout( $stream );

        if( !empty( $this->fanoutCache ) ) {
          $this->binarySearch( $stream, $sha, $onFound );
        }

        return 0;
      },
      0
    );
  }

  private function ensureFanout( StreamReader $stream ): void {
    if( empty( $this->fanoutCache ) ) {
      $stream->seek( 0 );

      $head = $stream->read( 8 );

      if( $head === "\377tOc\0\0\0\2" ) {
        $data = $stream->read( 1024 );

        $this->fanoutCache = array_values( unpack( 'N*', $data ) );
      }
    }
  }

  private function binarySearch(
    StreamReader $stream,
    string $sha,
    callable $onFound
  ): void {
    $byte  = ord( $sha[0] );
    $start = $byte === 0 ? 0 : $this->fanoutCache[$byte - 1];
    $end   = $this->fanoutCache[$byte];

    if( $end > $start ) {
      $low    = $start;
      $high   = $end - 1;
      $result = 0;

      while( $result === 0 && $low <= $high ) {
        $mid = ($low + $high) >> 1;
        $pos = 1032 + $mid * 20;
        $cmp = $this->readShaBytes( $stream, $pos );

        if( $cmp < $sha ) {
          $low = $mid + 1;
        } elseif( $cmp > $sha ) {
          $high = $mid - 1;
        } else {
          $result = $this->readOffset( $stream, $mid );
        }
      }

      if( $result !== 0 ) {
        $onFound( $this->packFile, $result );
      }
    }
  }

  private function readShaBytes( StreamReader $stream, int $pos ): string {
    if(
      $this->bufferOffset === -1 ||
      $pos < $this->bufferOffset ||
      $pos + 20 > $this->bufferOffset + 8192
    ) {
      $stream->seek( $pos );

      $this->bufferOffset = $pos;
      $this->buffer       = $stream->read( 8192 );
    }

    $offset = $pos - $this->bufferOffset;

    return substr( $this->buffer, $offset, 20 );
  }

  private function readOffset( StreamReader $stream, int $mid ): int {
    $total = $this->fanoutCache[255];
    $pos   = 1032 + $total * 24 + $mid * 4;

    $stream->seek( $pos );

    $packed = $stream->read( 4 );
    $offset = unpack( 'N', $packed )[1];

    if( $offset & 0x80000000 ) {
      $pos64 = 1032 + $total * 28 + ($offset & 0x7FFFFFFF) * 8;

      $stream->seek( $pos64 );

      $packed64 = $stream->read( 8 );
      $offset   = unpack( 'J', $packed64 )[1];
    }

    return (int)$offset;
  }
}