Predictor και LZWDecode στη Delphi με το HotPDF

Ένα stream με σήμανση /Predictor 12 δεν σημαίνει ότι κάθε γραμμή χρησιμοποιεί το φίλτρο PNG 2. Το HotPDF, το native VCL PDF component για Delphi και C++Builder, αντιμετωπίζει τις τιμές predictor 10 έως 15 ως μία οικογένεια: η πραγματική ετικέτα φίλτρου, 0 έως 4, είναι το πρώτο byte κάθε κωδικοποιημένης γραμμής, και η HPDFDecodePredictor διαβάζει και επικυρώνει αυτή την ετικέτα γραμμή προς γραμμή. Αυτή η διάκριση είναι το σχήμα σχεδόν κάθε bug σε αυτή τη γωνιά του PDF, γιατί τίποτα δεν σηκώνει σφάλμα όταν την κάνεις λάθος. Η αλυσίδα φίλτρων τρέχει, το raster έχει το μέγεθος που περίμενες, και η εικόνα βγαίνει σαν διαγώνιο θόρυβο ή σαν διαβάθμιση που παρεκκλίνει όλο και περισσότερο σε κάθε scanline. Οι πέντε αριθμοί στο /DecodeParms (ISO 32000-1 §7.4.4) κατά κύριο λόγο αλλάζουν το νόημα των bytes και όχι το μήκος τους, οπότε ένας λάθος αριθμός παράγει ευλογοφανή σκουπίδια αντί για σφάλμα

Γιατί το /Predictor 12 δεν σημαίνει φίλτρο PNG 2 σε κάθε γραμμή;

Επειδή ο αριθμός predictor λέει μόνο ότι «χρησιμοποιείται PNG prediction», όχι ποιο φίλτρο. Οι κωδικοποιητές PNG επιλέγουν ένα φίλτρο ανά scanline και το φίλτρο PDF κληρονομεί αυτή τη λογική, οπότε οι τιμές predictor 10 (None), 11 (Sub), 12 (Up), 13 (Average), 14 (Paeth) και 15 (Optimum) αποκωδικοποιούνται όλες με τον ίδιο τρόπο: το byte-ετικέτα στην αρχή κάθε γραμμής είναι αυτό που πρέπει να υπακούσει ο αποκωδικοποιητής. Η συνέπεια στη διάταξη μετράει εξίσου με τη σημασιολογία. Κάθε κωδικοποιημένη γραμμή έχει μήκος 1 + RowBytes bytes, άρα η είσοδος υπερβαίνει την έξοδο ακριβώς κατά τον αριθμό γραμμών, και ένα stream του οποίου το μήκος δεν είναι ακέραιο πολλαπλάσιο του RowBytes + 1 είναι εξ ορισμού περικομμένο. Το HotPDF ελέγχει αυτό το όριο πριν αγγίξει κανένα byte, απορρίπτει κάθε ετικέτα πάνω από 4 με Invalid PNG predictor row tag, και διαβάζει την προηγούμενη γραμμή απευθείας από τον ενιαίο buffer εξόδου αντί να υλοποιεί δισδιάστατο πίνακα γραμμών. Τα φίλτρα 1 και 3 ανατρέχουν BytesPerPixel θέσεις πίσω μέσα στην τρέχουσα γραμμή, το φίλτρο 2 διαβάζει κατευθείαν προς τα πάνω, το φίλτρο 4 τρέχει την επιλογή Paeth πάνω σε αριστερά, πάνω και πάνω-αριστερά — και και τα τέσσερα λειτουργούν πάνω σε ήδη ανακατασκευασμένη έξοδο, γι' αυτό η γραμμή-πάνω πρέπει να είναι η αποκωδικοποιημένη γραμμή και ποτέ η φιλτραρισμένη είσοδος

uses
  HPDFPredictor;

var
  Filtered, Raster: AnsiString;
  ErrorText: string;
begin
  // /DecodeParms << /Predictor 12 /Colors 3 /BitsPerComponent 8 /Columns 1024 >>
  if HPDFTryDecodePredictor(Filtered, 12, 3, 8, 1024,
       Int64(1024) * 3 * 8192, Raster, ErrorText) then
    ConsumeRaster(Raster)
  else
    LogStreamDefect('predictor', ErrorText);   // no exception, no partial raster
end;

Το όρισμα MaxOutputBytes δεν είναι διακοσμητικό. Ένα στάδιο predictor είναι στην ουσία ένα στάδιο αποσυμπίεσης, και μια εχθρική ή απλώς λανθασμένη τιμή /Columns μετατρέπει λίγα kilobytes εισόδου σε αίτημα εκχώρησης πολλών gigabyte. Το HotPDF υπολογίζει πρώτα bits ανά γραμμή, bytes ανά γραμμή και συνολικό μέγεθος raster σε Int64, αρνείται γεωμετρίες που υπερχειλίζουν, και τηρεί το ανώτατο όριο που δίνει ο καλών. Δώσε ένα πραγματικό όριο προερχόμενο από το dictionary της εικόνας, και ο τρόπος αποτυχίας γίνεται καταγεγραμμένο μήνυμα αντί για διάλογο out-of-memory σε μηχάνημα πελάτη

Γιατί ο TIFF Predictor 2 καταστρέφει εικόνες 4 bit;

Επειδή ο Predictor 2 είναι οριζόντια διαφοροποίηση ανά δείγμα, όχι ανά byte, και στα 1, 2 ή 4 bits ανά component πολλά δείγματα μοιράζονται ένα byte. Η συνηθισμένη υλοποίηση προσθέτει το byte N-Colors στο byte N, κάτι που τυχαίνει να είναι σωστό στα 8 bits ανά component και είναι σιωπηρά λάθος παντού αλλού. Ένα 8-bit RGB scan αποκωδικοποιείται τέλεια, και μετά ο ίδιος κώδικας καταστρέφει μια 4-bit indexed εικόνα την πρώτη φορά που εμφανίζεται στην παραγωγή

Η σωστή αριθμητική λειτουργεί μέσα στο bit field. Το HotPDF διατρέχει τα δείγματα από τον δείκτη Colors έως Colors * Columns - 1, εξάγει το δείγμα και τον γείτονά του αριστερά από το ίδιο component με μάσκα (1 shl BitsPerComponent) - 1 στην κατάλληλη μετατόπιση, τα προσθέτει modulo αυτής της μάσκας, και γράφει το αποτέλεσμα πίσω χωρίς να διαταράξει τα άλλα δείγματα που είναι πακεταρισμένα στο ίδιο byte. Η ουρά έχει επίσης σημασία: μια γραμμή είναι padded σε όριο byte, οπότε τα bits padding μετά το τελευταίο δείγμα πρέπει να παραμείνουν ανέπαφα αντί να μπλεχτούν στην αριθμητική. Στα 16 bits ανά component κάθε δείγμα είναι ένα ζευγάρι bytes σε big-endian και η πρόσθεση τυλίγεται στο $FFFF σε όλο το ζεύγος αντί να μεταφέρεται ανάμεσα στα bytes ανεξάρτητα· στα 8 bits η απλή επανάληψη byte-προς-byte είναι σωστή, προχωρώντας κατά Colors ώστε το κόκκινο να συσσωρεύεται έναντι κόκκινου και το alpha έναντι alpha. Σε κάθε παραλλαγή το πρώτο pixel μιας γραμμής είναι κυριολεκτικό, ποτέ διαφορά, και η αναδρομή ξεκινά ξανά σε κάθε όριο γραμμής — η πρόβλεψη TIFF δεν διαβάζει ποτέ τη γραμμή από πάνω, που είναι όλη η διαφορά ανάμεσα σε αυτήν και την οικογένεια PNG

Τι ελέγχει πραγματικά το EarlyChange στο LZWDecode;

Ελέγχει πότε ο αναγνώστης διευρύνει το μέγεθος κωδικού κατά ένα bit, και το να είσαι έναν κωδικό εκτός συγχρονισμού διαφθείρει όλα όσα ακολουθούν. Το HotPDF εκφράζει τον κανόνα ως ένα ενιαίο αναλλοίωτο: μετά την προσθήκη μιας εγγραφής στο dictionary, η επόμενη ανάγνωση διευρύνει όταν το NextCode φτάσει σε (1 shl CodeSize) - Ord(EarlyChange). Με /EarlyChange 1, την προεπιλογή του ISO 32000-1 §7.4.4, η αλλαγή συμβαίνει έναν κωδικό νωρίτερα· με /EarlyChange 0 συμβαίνει ακριβώς στο όριο. Και τα δύο εμφανίζονται σε πραγματικά αρχεία και τίποτα στο bitstream δεν σου λέει ποιο χρησιμοποίησε ο κωδικοποιητής. Η υπόλοιπη μηχανή καταστάσεων πρέπει να κινείται σε πλήρη συγχρονισμό: ένας κωδικός clear επαναφέρει μαζί το μέγεθος κωδικού, τη μάσκα bits, τον επόμενο ελεύθερο κωδικό και την αποθήκευση φράσεων, και ο κωδικός end-of-information διαβάζεται στο όποιο πλάτος ισχύει εκείνη τη στιγμή, όχι στα αρχικά 9 bits. Το HotPDF ξεκινά στο InitialCodeSize 9, οριοθετεί το μέγεθος κωδικού στο 12 και το dictionary στις 4096 εγγραφές, και ορίζει το FillOrder ως foTop εξ ορισμού επειδή το PDF πακετάρει κωδικούς με το bit υψηλής τάξης πρώτο — το foBottom υπάρχει για streams τύπου TIFF που δεν το κάνουν

uses
  HPDFLZW;

var
  Decoder: TPDFLZWDecompressor;
  Parms: TPDFLZWParms;
  Plain: AnsiString;
begin
  Decoder := TPDFLZWDecompressor.Create;
  try
    Decoder.EarlyChange := True;      // /EarlyChange 1 is the PDF default
    Decoder.FillOrder := foTop;       // high-order bit first
    Decoder.MaxOutputBytes := 256 * 1024 * 1024;
    Decoder.RequireInitialClear := False;
    Decoder.RequireEndOfInformation := False;

    Parms.Predictor := 12;
    Parms.Colors := 3;
    Parms.BitsPerComponent := 8;
    Parms.Columns := 1024;
    Parms.ExpandedTo8Bit := False;
    Parms.ColorSpace := 'DeviceRGB';

    if Decoder.TryDecompress(RawStreamBytes, Parms, Plain) then
      LogDecodeStats(Decoder.PeakCodeSize, Decoder.DictionaryAdds,
        Decoder.KwKwKExpansions, Decoder.OutputBytes)
    else
      LogStreamDefect('lzw', Decoder.LastError);
  finally
    Decoder.Free;
  end;
end;

Τα στατιστικά υπάρχουν για διάγνωση, όχι για επίδειξη. Όταν ένα αρχείο αποκωδικοποιείται στο σωστό μήκος αλλά τα λάθος pixel, το PeakCodeSize και το DictionaryAdds σου λένε αμέσως αν ο αναγνώστης διεύρυνε ποτέ εκεί που το έκανε ο εγγραφέας. Γύρισε το EarlyChange, αποκωδικοποίησε ξανά, σύγκρινε τα δύο: αν οι αριθμοί κινούνται, έχεις την απάντησή σου σε ένα πέρασμα αντί να περάσεις βήμα-βήμα έναν bit reader

Ο κλάδος KwKwK, και πότε ένα stream θα πρέπει απλώς να αποτύχει

Η μία νόμιμη περίπτωση που μοιάζει παράνομη είναι το Code = NextCode, και το HotPDF το χειρίζεται κατασκευάζοντας την εγγραφή πριν την εκπέμψει. Ένας κωδικοποιητής μπορεί να εκπέμψει τον κωδικό για μια φράση που ορίζει στο ίδιο βήμα, κάτι που συμβαίνει όποτε η είσοδος περιέχει ένα μοτίβο της μορφής K w K w K· ο αποκωδικοποιητής δεν μπορεί να αναζητήσει αυτόν τον κωδικό γιατί δεν υπάρχει ακόμα, οπότε πρέπει να χτίσει το Previous + First(Previous), να το προσθέσει ως νέα εγγραφή, και να εκπέμψει την εγγραφή που μόλις δημιούργησε. Το HotPDF τα μετράει στο KwKwKExpansions και επαληθεύει διασταυρωτά ότι ο κωδικός που πρόσθεσε είναι ο κωδικός που του ζητήθηκε. Οτιδήποτε πάνω από το NextCode είναι διαφθορά, και εκεί ένας αποκωδικοποιητής πρέπει να σταματήσει αντί να αυτοσχεδιάσει: το HotPDF σηκώνει εξαίρεση σε μελλοντικό κωδικό, σε πρόθεμα dictionary που δείχνει έξω από την περιοχή φράσεων, σε πλήρες dictionary, και σε πρώτο κωδικό που δεν είναι κυριολεκτικός. Δύο διακόπτες αυστηρότητας είναι σκόπιμα απενεργοποιημένοι εξ ορισμού, το RequireInitialClear και το RequireEndOfInformation, γιατί αρκετά PDF παραγωγής παραλείπουν τον αρχικό κωδικό clear ή εξαντλούν τα δεδομένα χωρίς τερματιστή. Ενεργοποίησέ τα όταν επικυρώνεις τη δική σου έξοδο, άφησέ τα απενεργοποιημένα όταν καταναλώνεις αρχεία από το πεδίο

Πού διαβάζεται πραγματικά το /DecodeParms στην πλευρά του φορτωμένου εγγράφου

Το HotPDF επιλύει το /DecodeParms ή τη σύντμησή του /DP στο dictionary του stream εικόνας, δέχεται είτε dictionary είτε array και παίρνει το τελευταίο στοιχείο όταν είναι array, και μετά μεταφέρει τα Predictor, Colors, BitsPerComponent, Columns και EarlyChange στο μονοπάτι raster. Η περίπτωση του array είναι αυτή που ξεχνούν οι περισσότεροι: ένα stream φιλτραρισμένο με [/ASCII85Decode /FlateDecode] φέρει ένα παράλληλο array παραμέτρων, και οι ρυθμίσεις predictor ανήκουν στο τελευταίο φίλτρο, όχι στο πρώτο

var
  Pdf: THotPDF;
  Info: THPDFLoadedImageInfo;
  Bmp: TBitmap;
  I: Integer;
begin
  Pdf := THotPDF.Create(nil);
  try
    if Pdf.LoadFromFile('scanned.pdf', '') > 0 then
      for I := 0 to Pdf.GetLoadedImageCount - 1 do
        if Pdf.GetLoadedImageInfo(I, Info) then
        begin
          Bmp := Pdf.ExtractLoadedImage(I);   // nil when the raster is unusable
          if Bmp <> nil then
          try
            Bmp.SaveToFile(Format('image-%d.bmp', [I]));
          finally
            Bmp.Free;
          end;
        end;
  finally
    Pdf.Free;
  end;
end;

Αξίζει να αναφερθεί ένα ιστορικό ελάττωμα σε αυτό το μονοπάτι, γιατί η κατηγορία του bug επαναλαμβάνεται. Η παλιά ρουτίνα Flate-με-παραμέτρους δημιουργούσε ένα stream αποσυμπίεσης και μετά αντέγραφε από την αρχική συμπιεσμένη είσοδο, οπότε το στάδιο predictor λάμβανε συμπιεσμένα bytes και τα «απο-προέβλεπε» ευσυνείδητα: πάντα λάθος, ποτέ σφάλμα. Ο τρέχων κώδικας διαβάζει μόνο από τον αποκωδικοποιητή πριν παραδώσει το αποτέλεσμα στον κοινό predictor, και απορρίπτει ένα raster μικρότερο από το υπολογισμένο μέγεθος αντί να καταφεύγει στα ακόμα συμπιεσμένα bytes — μια εναλλακτική που παλιότερα μετέτρεπε μια αποτυχία αποκωδικοποίησης σε κατεστραμμένο bitmap. Η ίδια υλοποίηση predictor εξυπηρετεί τώρα και τα cross-reference streams, κάτι που αποτελεί χρήσιμη συνέπεια αν δουλεύεις επίσης με object streams και incremental updates, ενώ η γύρω μηχανική εξαγωγής καλύπτεται στο συνοδευτικό άρθρο για την εξαγωγή φορτωμένων εικόνων και τα decode filters τους. Εικόνες που φτάνουν ως DCTDecode ή JPXDecode δεν φτάνουν καθόλου στον predictor· φέρουν το δικό τους συμπιεσμένο μοντέλο pixel

Απόδοση: μια ενιαία περιοχή φράσεων έναντι strings ανά εγγραφή

Η αντικατάσταση του dictionary strings ανά εγγραφή με μια ενιαία περιοχή φράσεων μέτρησε περίπου 1,61 φορές ταχύτερη σε μια παθολογική είσοδο: 1558 MiB/s έναντι 969 MiB/s σε ένα benchmark όπου η μεγαλύτερη μεμονωμένη φράση φτάνει τα 7.370.880 bytes. Το σχήμα αυτής της εισόδου εξηγεί το χάσμα, γιατί οι κλασικές υλοποιήσεις επιλέγουν μία από δύο κακές ανταλλαγές. Ένα dictionary τιμών AnsiString εκχωρεί και αντιγράφει ένα νέο string για καθεμία από έως 4096 εγγραφές, με κάθε νέα εγγραφή να αντιγράφει ολόκληρο τον γονέα της· ένα stack prefix/suffix αποφεύγει αυτή τη μνήμη εντελώς αλλά ανακατασκευάζει κάθε φράση διατρέχοντας την αλυσίδα προς τα πίσω byte-byte και αντιστρέφοντάς την, κάτι που είναι εντάξει για συνηθισμένο κείμενο και επώδυνο όταν μια φράση φτάνει τα megabytes. Το HotPDF προσαρτά κάθε φράση συνεχόμενα σε μια περιοχή που μεγαλώνει γεωμετρικά, ευρετηριάζει τις εγγραφές με offset και μήκος, και εκπέμπει μια φράση με ένα μοναδικό Move στον buffer εξόδου. Το τίμιο κόστος είναι η μνήμη: μια περιοχή που κρατά κάθε φράση πλήρως οριοθετείται από το άθροισμα όλων των μηκών φράσεων και όχι από τον αριθμό εγγραφών, που είναι ακριβώς γιατί υπάρχει το MaxOutputBytes τόσο στον αποσυμπιεστή όσο και στον predictor. Παράγε αυτό το όριο από όσα ισχυρίζεται το dictionary της εικόνας ότι πρέπει να είναι το raster, και ένα ψευδόμενο stream αποτυγχάνει γρήγορα

Ο αποσυμπιεστής LZW, ο κοινός predictor και το μονοπάτι εξαγωγής φορτωμένων εικόνων που παρουσιάζονται εδώ διατίθενται ως μέρος του τυπικού HotPDF Component για Delphi και C++Builder, με την πλήρη αναφορά φίλτρων και DecodeParms στη σελίδα του προϊόντος