PDFlibPas JBIG2 halftone: HSKIP και αρνητικά offsets

Το PDFlibPas διόρθωσε δύο ανεξάρτητα ελαττώματα στον εγγενή decoder του για halftone regions JBIG2: στο v3.539.37 η μάσκα παράλειψης HSKIP δεικτοδοτείται ως HSKIP[ng, mg] όπως την ορίζει το ITU-T T.88 §6.6.5.1, και στο v3.539.38 πλέγματα που φτάνουν αρνητικές συντεταγμένες, μέσω αρνητικού HGX ή HGY ή μέσω περιστροφής, τοποθετούνται με αληθινή ολίσθηση floor. Πριν από εκείνες τις εκδόσεις, τα επηρεαζόμενα halftone regions βγαίνανε αλαμπουρνέζικα ή μετατοπισμένα, χωρίς κανένα σφάλμα. Και τα δύο bugs κρύβονταν πίσω από test δεδομένα που τύχαινε να είναι συμμετρικά ή μη αρνητικά, και το δεύτερο ανάβει μια ιδιότητα του Delphi και του Free Pascal που δαγκώνει πολύ έξω από το JBIG2: το shr σε προσγεσιομένο ακέραιο είναι λογική ολίσθηση, όχι η αριθμητική >> που υποθέτει το πρότυπο

Τα halftone regions είναι ο λιγότερο συνηθισμένος τύπος region του JBIG2, οπότε ένας decoder μπορεί να επεξεργαστεί χιλιάδες σαρωμένα έγγραφα πριν συναντήσει μια υποβαθμισμένη φωτογραφία κωδικοποιημένη ως τέτοια. Όταν το κάνει, η αποτυχία είναι άσχημη: το αρχείο κάνει parse, τα μήκη των segments αθροίζονται, η σελίδα έχει το σωστό μέγεθος, και το region είναι σκουπίδια

Τι αποκωδικοποιεί στην πραγματικότητα ένα halftone region JBIG2;

Ένα halftone region JBIG2 είναι ένα πλέγμα από μικρά bitmaps διαλεγμένα από ένα pattern dictionary, και η αληθινή δουλειά του decoder είναι ο υπολογισμός ενός δείκτη για κάθε κελί του πλέγματος και της θέσης pixel όπου προσγειώνεται εκείνο το κελί. Το pattern dictionary κρατά HNUMPATS patterns των HPW × HPH pixels. Το segment του halftone region περιγράφει μετά ένα πλέγμα HGW στηλών επί HGH γραμμών και μια εικόνα gray-scale του ίδιου μεγέθους, κωδικοποιημένη ως Gray-coded bitplanes. Κάθε bitplane αποκωδικοποιείται με τη διαδικασία generic region πάνω σε bitmap HGW × HGH, με το σημαντικότερο plane πρώτο, και τα planes μαζί δίνουν σε κάθε κελί τον δείκτη pattern του

Η τοποθέτηση κελιών χρησιμοποιεί αριθμητική σταθερής υποδιαστολής με κλάσμα 8 bit. Η αρχή του πλέγματος HGX, HGY είναι ένα ζεύγος 32-bit τιμών, και το διάνυσμα πλέγματος HRX, HRY περιγράφει το βήμα ανάμεσα σε γειτονικά κελιά, που επιτρέπει στραμμένο πλέγμα. Για γραμμή πλέγματος mg και στήλη πλέγματος ng, το T.88 §6.6.5 υπολογίζει τη θέση pixel ως:

• x = (HGX + mg × HRY + ng × HRX) >> 8
• y = (HGY + mg × HRX − ng × HRY) >> 8

Η μάσκα παράλειψης μπαίνει μέσω της προαιρετικής σημαίας HENABLESKIP. Όταν η σημαία είναι ορισμένη, το §6.6.5.1 χτίζει bitmap HGW × HGH HSKIP και θέτει HSKIP[ng, mg] σε 1 για κάθε κελί του οποίου το pattern βρίσκεται εντελώς έξω από το region: x + HPW <= 0, x >= HBW, y + HPH <= 0 ή y >= HBH. Τα bitplanes gray-scale αποκωδικοποιούνται μετά με εκείνη τη μάσκα ως bitmap παράλειψης του generic region, οπότε ο αριθμητικός decoder ούτε διαβάζει ούτε ενημερώνει context για παραλειμμένο κελί. Decoder και encoder πρέπει να συμφωνούν σε κάθε bit του HSKIP, αλλιώς οι δύο αριθμητικοί κωδικοποιητές χάνουν το βήμα

Γιατί μια αντεστραμμένη μάσκα HSKIP έσπασε μόνο μη τετραγωνικά πλέγματα;

Η μάσκα παράλειψης γραφόταν με αντεστραμμένες συντεταγμένες, και μόνο ένα μη τετραγωνικό πλέγμα την αποκάλυπτε, επειδή ένα τετραγωνικό πλέγμα κρατά κάθε αντεστραμμένη συντεταγμένη μέσα στη μάσκα. Το PDFlibPas αποθηκεύει bitmaps με accessor pixel (column, row), και ο κώδικας που έχτιζε τη μάσκα περνούσε (mg, ng), γραμμή πρώτη. Ο decoder bitplanes gray-scale διαβάζει τη μάσκα σωστά ως (ng, mg). Ο βρόχος τοποθέτησης patterns τη διάβαζε πίσω στην αντεστραμμένη σειρά του builder, οπότε οι δύο συμφωνούσαν, και μια αναθεώρηση μόνο της λογικής τοποθέτησης θα την περνούσε. Μια παγίδα ονομάτων την έκανε χειρότερη: στον βρόχο τοποθέτησης η μεταβλητή που λέγεται col επαναλαμβάνει γραμμές πλέγματος και το Row επαναλαμβάνει στήλες πλέγματος

Πάρτε το πλέγμα 5 × 3 από patterns 4 × 4 πάνω σε region 16 × 8 που το v3.539.37 χρησιμοποιεί ως regression περίπτωσή του. Με HRX = 1024 και HRY = 0, η στήλη πλέγματος 4 προσγειώνεται σε x = 16 και η γραμμή πλέγματος 2 σε y = 8, και οι δύο έξω από το region. Η σωστή μάσκα σημειώνει επτά κελιά: όλη τη στήλη 4 και όλη τη γραμμή 2. Οι αντεστραμμένες εγγραφές προσπαθούσαν να θέσουν pixels σε δείκτες γραμμών 3 και 4 σε μάσκα μόλις τριών γραμμών, και ο setter του bitmap αγνοούσε αθόρυβα εκείνες τις εκτός ορίων εγγραφές. Εκεί που επιβίωσε ήταν η στήλη 2, γραμμές 0 έως 2. Ο decoder παράλειπε επομένως δύο κελιά που είχε κωδικοποιήσει ο encoder, και αποκωδικοποιούσε έξι κελιά που ο encoder είχε παραλείψει

Ο αριθμητικός decoder δεν αποτυγχάνει όταν συμβεί αυτό. Αποκωδικοποιεί extra pixels από bits που ανήκουν σε μεταγενέστερα κελιά, τα contexts του διαβάζουν λάθος γείτονες, και κάθε δείκτης pattern μετά την πρώτη ασυμφωνία είναι θόρυβος, γι αυτό το σύμπτωμα ήταν αλαμπουρνέζικο region αντί για λίγα μετατοπισμένα κελιά. Σε τετραγωνικό πλέγμα το ίδιο bug είναι συχνά αόρατο: καμία αντεστραμμένη συντεταγμένη δεν φεύγει από τη μάσκα, και όταν τα εκτός region κελιά είναι συμμετρικά ως προς τη διαγώνιο, ένα πλέγμα που υπερκαλύπτει δεξιά και κάτω άκρη κατά τον ίδιο αριθμό κελιών για παράδειγμα, η αντεστραμμένη μάσκα είναι bit-προς-bit η σωστή. Το HENABLESKIP είναι επίσης προαιρετικό, πρέπει να είναι 0 όταν η εικόνα gray-scale είναι MMR-coded, και σπάνια ορίζεται από encoders, οπότε το bug είχε ελάχιστους τρόπους να εμφανιστεί. Από το v3.539.37 ο builder γράφει HSKIP[ng, mg] και ο βρόχος τοποθέτησης διαβάζει την ίδια σειρά

Γιατί αποτυγχάνουν σε τρία στρώματα τα αρνητικά offsets πλέγματος halftone;

Ένα halftone πλέγμα που ξεκινά αριστερά ή πάνω από το region του έσπασε το PDFlibPas σε τρία ξεχωριστά σημεία, και κάθε ελάττωμα κρύβει το επόμενο. Το T.88 επιτρέπει αυτή τη γεωμετρία σκόπιμα. Ένας encoder που στοιχίζει το screen του στη σελίδα αντί στο region, ή χρησιμοποιεί στραμμένο πλέγμα, παράγει φυσικά αρνητικές γωνίες κελιών που το region κόβει. Το v3.539.38 διόρθωσε και τα τρία στρώματα μαζί, επειδή η διόρθωση οποιουδήποτε μόνου άλλαζε μόνο το σύμπτωμα

Στρώμα 1: προσγεσιομένο πεδίο διαβασμένο ως άπροσγεσιομένο

Το T.88 §7.4.5.1.2 ορίζει τα HGX και HGY ως προσγεσιομένες 32-bit τιμές, αλλά ο decoder τα διάβαζε με τον ίδιο 32-bit βοηθό που χρησιμοποιούσε για άπροσα πεδία, και εκείνος ο βοηθός συμπίεζε κάθε αρνητικό αποτέλεσμα σε 0. Ένα πλέγμα που προοριζόταν να ξεκινήσει σε HGX = -900 μετακινούνταν αθόρυβα στην αρχή του region. Στη regression περίπτωση του v3.539.38 όλη η εικόνα βγαινε δύο γραμμές πιο κάτω. Ο clamp εξηγεί επίσης γιατί τα άλλα δύο ελαττώματα επιβίωσαν τόσο: με την αρχή αναγκαστικά μη αρνητική, αρνητική συντεταγμένη μπορούσε να εμφανιστεί μόνο μέσω στραμμένου πλέγματος με HRY > 0, όπου το y = HGY + mg × HRX − ng × HRY πέφτει κάτω από το μηδέν για μεταγενέστερες στήλες πλέγματος

Στρώμα 2: το shr δεν είναι >> 8

Το T.88 γράφει >> 8 και εννοεί αριθμητική ολίσθηση, που στρογγυλοποιεί προς μείον άπειρο. Ο decoder τη μετέφρασε ως shr 8. Στο Delphi και το Free Pascal, το shr σε προσγεσιομένο ακέραιο είναι λογική ολίσθηση: το bit πρόσημου ολισθαίνει μέσα ως μηδέν. Για Integer που κρατά -512, το shr 8 δίνει 16777214 αντί για -2. Ένα pattern που έπρεπε να σχεδιαστεί σε y = -2 και να κοπεί στο κάτω μισό του στάλθηκε 16 εκατομμύρια γραμμές πιο κάτω και απορρίφθηκε ως εκτός region. Τίποτα δεν κατέρρευσε· η πάνω γραμμή του halftone απλώς εξαφανίστηκε

Στρώμα 3: σύγκριση σταθερής υποδιαστολής αντί για pixels

Το test παράλειψης συνέκρινε τιμές σταθερής υποδιαστολής, όχι θέσεις pixels, και οι δύο δεν είναι ισοδύναμες μόλις το κλάσμα γίνει μη μηδενικό. Ο αρχικός κώδικας αποφεύγει την λογική ολίσθηση ελέγχοντας xx + HPW × 256 <= 0 στην αολίσθητη τιμή, υποτιθέμενο ισοδύναμο του test του T.88. Με HGX = -900 και pattern 4 pixels, αυτό δίνει -900 + 1024 = 124, που είναι θετικό, οπότε το κελί δεν παραλείπεται. Το πρότυπο ολισθαίνει πρώτο: floor(-900 / 256) = -4, και -4 + 4 = 0 πληροί το x + HPW <= 0, οπότε το κελί βρίσκεται εντελώς έξω και πρέπει να παραλειφθεί. Ο encoder το παραλείπε, ο decoder το αποκωδικοποιεί, και η εικόνα gray-scale παρέκκλινε ακριβώς όπως στην περίπτωση της αντεστραμμένης μάσκας

Η regression περίπτωση του v3.539.38 χρησιμοποιεί πλέγμα 4 × 3 από patterns 4 × 4 σε HGX = -900, HGY = -512, HRX = 1024 πάνω σε region 12 × 10. Οι στήλες πλέγματος προσγειώνονται σε x = -4, 0, 4 και 8, οπότε η στήλη 0 είναι εντελώς έξω και ανήκει στο HSKIP· οι γραμμές πλέγματος προσγειώνονται σε y = -2, 2 και 6, οπότε η γραμμή 0 πρέπει να κοπεί στις κάτω δύο σειρές pixels της αντί να απορριφθεί. Η διόρθωση των στρωμάτων ένα τη φορά αναπαράγει τη στοίβα:

Διορθωμένα ελαττώματα	Αποκωδικοποιημένο region
Κανένα (πριν το v3.539.38)	Πλέγμα τραβηγμένο στην αρχή, όλη η εικόνα δύο γραμμές πιο κάτω
Μόνο προσγεσιομένη ανάγνωση HGX / HGY	Λείπει η πρώτη γραμμή πλέγματος, το υπόλοιπο αλαμπουρνέζικο από την παρέκκλιση του test παράλειψης
Προσγεσιομένη ανάγνωση, ολίσθηση floor και test παράλειψης σε χώρο pixels	Πανομοιότυπο, pixel προς pixel, με τη σελίδα υπολογισμένη από το T.88 §6.6.5 και με δύο ανεξάρτητους reference decoders

Η διόρθωση είναι ένας βοηθός, HalftoneGridPixel, κοινός στον builder μάσκας παράλειψης και στον βρόχο τοποθέτησης. Σωρεύει τη συντεταγμένη σε Int64 ώστε ένα μεγάλο γινόμενο mg × HRX να μη γυρίσει γύρω, διαιρεί με 256 στρογγυλοποιώντας προς μείον άπειρο, και συμπιέζει σε ±MaxInt div 2 ώστε ένα κατεστραμμένο πλέγμα να μη κάνει overflow σε μεταγενέστερη αριθμητική bitmap. Το test παράλειψης συγκρίνει πλέον εκείνες τις τιμές pixels με τα HPW, HPH, HBW και HBH, ακριβώς όπως το λέει το §6.6.5.1

Πώς γράφετε αριθμητική ολίσθηση δεξιά στο Delphi;

Το Delphi δεν έχει τελεστή αριθμητικής ολίσθησης, οπότε μια σωστή προσγεσιομένη ολίσθηση δεξιά πρέπει να γραφτεί ως διαίρεση floor, και το σκέτο div δεν είναι εκείνη η διαίρεση. Το div κόβει προς το μηδέν. Για μη αρνητικές τιμές περικοπή και floor συμφωνούν, και συμφωνούν επίσης για αρνητικές τιμές που είναι ακριβή πολλαπλάσια του διαιρέτη, γι αυτό το -512 div 256 = -2 φαίνεται μια χαρά σε γρήγορο test. Διαφωνούν παντού αλλού: το -900 div 256 είναι -3, ενώ το floor είναι -4, και το -1 div 256 είναι 0, ενώ το floor είναι -1. Μια συντεταγμένη JBIG2 με μη μηδενικό κλάσμα είναι ακριβώς η περίπτωση όπου το div δίνει λάθος pixel

Στους μεταγλωττιστές Delphi Win32 και Win64, μια μεταβλητή Integer που κρατά -512 ολισθημένη δεξιά κατά 8 δίνει 16777214, και μια Int64 που κρατά -512 δίνει 72057594037927934. Το Free Pascal επίσης ορίζει το shr ως λογική ολίσθηση και παραδίδει SarLongint και SarInt64 στη unit System του για την αριθμητική εκδοχή, αλλά εκείνες οι συναρτήσεις δεν υπάρχουν στο Delphi, οπότε κώδικας κοινός στους δύο μεταγλωττιστές χρειάζεται τον δικό του βοηθό:

// Διαίρεση floor: στρογγυλοποιεί προς μείον άπειρο για οποιοδήποτε πρόσημο των A και B.
// Το B δεν πρέπει να είναι 0, και το FloorDiv(Low(Integer), -1) κάνει overflow όπως ακριβώς το div
function FloorDiv(A, B: Integer): Integer;
begin
  Result := A div B;
  if (A mod B <> 0) and ((A < 0) <> (B < 0)) then
    Dec(Result);
end;

// Αριθμητική ολίσθηση δεξιά (το ">>" της C και του T.88 σε προσγεσιομένες τιμές).
// Για αρνητικό Value, το not Value = -Value - 1 είναι μη αρνητικό, ώστε το
// λογικό shr είναι ασφαλές εκεί, και το εξωτερικό not γυρνά το αποτέλεσμα πίσω
function SarInt32(Value: Integer; Shift: Integer): Integer;  // Shift 0..31
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

function SarInt64(Value: Int64; Shift: Integer): Int64;      // Shift 0..63
begin
  if Value >= 0 then
    Result := Value shr Shift
  else
    Result := not ((not Value) shr Shift);
end;

Το κόλπο με το not δεν ολισθαίνει ποτέ αρνητικό αριθμό, οπότε δεν εξαρτάται από το πώς μεταχειρίζεται ο μεταγλωττιστής το bit πρόσημου, και δεν κάνει ποτέ overflow, συμπεριλαμβανομένου του Low(Integer). Και οι δύο βοηθοί ταίριαξαν σε reference floor Int64 πάνω από αρκετά εκατομμύρια τιμές, κάθε ολίσθηση από 0 έως 31 και τα άκρα Low(Integer) και High(Integer) σε Delphi Win32, Delphi Win64 και Free Pascal x86_64. Ένας έλεγχος υγείας που αξίζει να κρατήσετε σε κάθε unit test που αγγίζει συντεταγμένες:

var
  V: Integer;
begin
  V := -900;
  Writeln(V shr 8);           // 16777212  λογική ολίσθηση, το παλιό bug
  Writeln(V div 256);         // -3        περικοπή προς το μηδέν
  Writeln(FloorDiv(V, 256));  // -4        τι εννοεί το T.88 με >> 8
  Writeln(SarInt32(V, 8));    // -4
end;

Το Math.Floor(V / 256) επιστρέφει επίσης -4, αλλά η παράκαμψή του μέσω Double χάνει ακρίβεια για τιμές Int64 πάνω από 2⁵³, οπότε η ακέραια γεωμετρία πρέπει να μένει σε ακέραιους

Ποιες κλήσεις PDFlibPas τρέχουν τον decoder halftone;

Ο decoder halftone JBIG2 τρέχει όταν το PDFlibPas αποδίδει σελίδα με τον ενσωματωμένο renderer, επειδή η απόδοση θέλει pixels. Τα RenderPageToFile και RenderPageToStream φτάνουν και τα δύο εκεί μέσω των image streams JBIG2Decode της σελίδας, οπότε η επανάληψη απόδοσης μιας σελίδας halftone είναι ο απευθείας τρόπος να επιβεβαιώσετε ότι το v3.539.38 αλλάζει την έξοδό σας. Ο ίδιος decoder χειρίζεται τους άλλους τύπους region του JBIG2, καλυμμένους στους custom Huffman πίνακες JBIG2 στον καθαρό Pascal decoder και στην αποκωδικοποίηση αρχείων JBIG2 random-access σε Delphi, και το αποδιδόμενο bitmap τροφοδοτεί μετατροπές όπως η απόδοση σελίδων PDF σε 1-bit monochrome

uses
  SysUtils, PDFlibrary;

var
  Lib: TPDFlib;
  Page: Integer;
begin
  Lib := TPDFlib.Create;
  try
    if Lib.LoadFromFile('scanned-halftone.pdf', '') <> 1 then
      raise Exception.CreateFmt('Load failed, error %d', [Lib.LastErrorCode]);
    for Page := 1 to Lib.PageCount do
      // Η απόδοση αποκωδικοποιεί κάθε region JBIG2, halftones συμπεριλαμβανομένων
      if Lib.RenderPageToFile(150, Page, PDF_RENDER_PNG,
        Format('page-%.3d.png', [Page])) <> 1 then
        Writeln('Page ', Page, ' was not rendered');
  finally
    Lib.Free;
  end;
end.

Η εξαγωγή εικόνων κανονικά παίρνει διαφορετική διαδρομή. Το GetPageImageList επιστρέφει εικόνες JBIG2 σε εγγενή μορφή, και το SaveImageListItemDataToFile ή το GetImageListItemDataToString σας παραδίδει ένα αυτόνομο αρχείο JBIG2 χτισμένο από τα bytes του stream: το header του αρχείου, τα δεδομένα JBIG2Globals και ένα segment end-of-file γύρω από τα δεδομένα σελίδας. Η ιδιότητα 400 του GetImageListItemIntProperty αναφέρει 6 για τέτοιο item. Τίποτα δεν αποκωδικοποιείται σε εκείνη τη διαδρομή, οπότε ένα εξαγμένο .jb2 που φαίνεται σωστό σε άλλο viewer ενώ η αποδιδόμενη σελίδα δείχνει θόρυβο ήταν τυπικό σημάδι αυτών των δύο bugs halftone:

var
  ListID, I: Integer;
begin
  Lib.SelectPage(1);
  ListID := Lib.GetPageImageList(0);
  if ListID = 0 then
    Exit;
  try
    for I := 1 to Lib.GetImageListCount(ListID) do
      if Lib.GetImageListItemIntProperty(ListID, I, 400) = 6 then  // αυτόνομο JBIG2
        Lib.SaveImageListItemDataToFile(ListID, I, 0,
          Format('page1-image%d.jb2', [I]));
  finally
    Lib.ReleaseImageList(ListID);
  end;
end;

Όταν masks ή μετατροπή χρωμάτων επιβάλλουν rendered εναλλακτική, το item επιστρέφει ως αποκωδικοποιημένο bitmap και ο decoder halftone τρέχει όντως. Περισσότερα για image lists στο Delphi PDF κείμενο, εικόνα και εξαγωγή γραμματοσειρών

Σύντομη αναφορά: κανόνες πλέγματος JBIG2 halftone

• Δεικτοδοτείτε τη μάσκα παράλειψης ως HSKIP[ng, mg], στήλη πλέγματος πρώτη, και διαβάστε την πίσω στην ίδια σειρά όπου κι αν τοποθετούνται κελιά (T.88 §6.6.5.1, διορθώθηκε στο PDFlibPas v3.539.37)
• Τεστάρετε κάθε κώδικα halftone ή πλέγματος με μη τετραγωνικό πλέγμα και ασύμμετρο σύνολο εκτός region κελιών, επειδή ένα τετραγωνικό πλέγμα μπορεί να κρύψει εντελώς αντεστραμμένο δείκτη
• Διαβάστε τα HGX και HGY ως προσγεσιομένες 32-bit τιμές (T.88 §7.4.5.1.2), ποτέ μέσω άπροσγεσιομένου βοηθού που συμπιέζει αρνητικά
• Μεταφράστε την ολίσθηση >> 8 του προτύπου ως διαίρεση floor με 256, όχι ως shr 8 και όχι ως div 256
• Τρέξτε το test παράλειψης σε ολισθημένες θέσεις pixels· η μορφή σταθερής υποδιαστολής διαφέρει όποτε το κλάσμα είναι μη μηδενικό, όπως δείχνει το HGX = -900 με pattern 4 pixels
• Σωρεύστε συντεταγμένες πλέγματος σε Int64 και συμπιέστε πριν τις παραδώσετε σε κώδικα bitmap, ώστε ένα κατεστραμμένο πλέγμα να μη κάνει overflow
• Αναβαθμίστε σε v3.539.38 ή νεότερο αν τα έγγραφά σας περιέχουν halftone regions με HENABLESKIP, αρνητικές αρχές πλέγματος ή στραμμένα πλέγματα

Το PDFlibPas αποδίδει, εξάγει και επεξεργάζεται PDF έγγραφα από Delphi και C++Builder με εγγενή Pascal decoder JBIG2 που τώρα χειρίζεται μάσκες παράλειψης halftone, αρνητικές αρχές πλέγματος και στραμμένα πλέγματα όπως ορίζει το T.88. Δείτε τη PDFlibPas Delphi PDF library για χαρακτηριστικά, εκδόσεις και δοκιμαστική λήψη