گرید Halftone در JBIG2 در PDFlibPas: ‏HSKIP و آفست منفی

‏PDFlibPas دو عیب مستقل در decoder ناحیهٔ halftone بومی JBIG2 خودش را فیکس کرد: در v3.539.37 ماسک skip یعنی HSKIP به‌شکل HSKIP[ng, mg] اندیس‌گذاری می‌شود همان‌طور که ITU-T T.88 §6.6.5.1 تعریفش می‌کند، و در v3.539.38 گریدهایی که از طریق HGX یا HGY منفی یا از طریق چرخش به مختصات منفی می‌رسند با یک shift کفی واقعی جاگذاری می‌شوند. قبل از آن releaseها ناحیه‌های halftone درگیر آشفته یا جابه‌جا بیرون می‌آمدند، بدون هیچ error ای. هر دو باگ پشت داده‌های تستی پنهان شده بودند که اتفاقاً متقارن یا نامنفی بودند، و دومی روی یک خاصیت از Delphi و Free Pascal سوار است که خیلی بیرون از JBIG2 هم گاز می‌گیرد: ‏shr روی یک عدد صحیح علامت‌دار یک shift منطقی است، نه آن >> حسابی که استاندارد فرض می‌کند

ناحیه‌های halftone کم‌یاب‌ترین نوع ناحیهٔ JBIG2 هستند، پس یک decoder می‌تواند هزاران سند اسکن‌شده را پردازش کند قبل از اینکه با یک عکس هالفتون‌شده که به‌آن شکل کد شده روبرو شود. وقتی می‌شود، خرابی زشت است: فایل parse می‌شود، طول سگمنت‌ها جمع می‌شوند، صفحه اندازهٔ درست را دارد، و ناحیه آشغال است

یک ناحیهٔ halftone در JBIG2 در واقع چه چیزی decode می‌کند؟

یک ناحیهٔ halftone در JBIG2 گریدی از بیت‌مپ‌های کوچک است که از یک pattern dictionary برداشته می‌شوند، و کار واقعی decoder محاسبهٔ یک اندیس برای هر سلول گرید و موقعیت پیکسلی است که آن سلول فرود می‌آید. ‏pattern dictionary ‏HNUMPATS الگوی HPW × ‏HPH پیکسلی نگه می‌دارد. سگمنت ناحیهٔ halftone بعد گریدی از HGW ستون در HGH ردیف و یک تصویر خاکستری هم‌اندازه را توصیف می‌کند که به‌شکل bitplaneهای Gray کد کد شده است. هر bitplane با رویهٔ ناحیهٔ generic روی یک بیت‌مپ HGW × ‏HGH decode می‌شود، صفحهٔ باارزش‌ترین بیت اول، و صفحه‌ها با هم به هر سلول اندیس الگویش را می‌دهند

جاگذاری سلول با حساب نقطه‌ثابت با کسری 8 بیتی انجام می‌شود. مبدأ گرید یعنی HGX و HGY یک جفت مقدار 32 بیتی است و بردار گرید یعنی HRX و HRY گام بین سلول‌های مجاور را توصیف می‌کند، که گرید چرخیده را ممکن می‌سازد. برای ردیف گرید mg و ستون گرید ng، ‏T.88 §6.6.5 موقعیت پیکسلی را چنین حساب می‌کند:

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

ماسک skip از طریق فلگ اختیاری HENABLESKIP وارد می‌شود. وقتی فلگ ست شده باشد، ‏§6.6.5.1 یک بیت‌مپ HGW × ‏HGH یعنی HSKIP می‌سازد و HSKIP[ng, mg] را برای هر سلولی که الگویش کلاً بیرون ناحیه است روی 1 می‌گذارد: ‏x + HPW <= 0، ‏x >= HBW، ‏y + HPH <= 0 یا y >= HBH. بعد bitplaneهای خاکستری با آن ماسک به‌عنوان بیت‌مپ skip ناحیهٔ generic decode می‌شوند، پس decoder حسابی نه context سلول skip‌شده را می‌خواند نه به‌روز می‌کند. decoder و encoder باید در هر بیت از HSKIP توافق داشته باشند، وگرنه دو coder حسابی از هم جا می‌افتند

چرا ماسک HSKIP جابه‌جاشده فقط گریدهای نامربعی را می‌شکست؟

ماسک skip با مختصات عوض‌شده نوشته می‌شد، و فقط یک گرید نامربع آن را لو می‌داد، چون گرید مربع هر مختصات عوض‌شده را داخل ماسک نگه می‌دارد. ‏PDFlibPas بیت‌مپ‌ها را با یک accessor پیکسلی به‌شکل (column, row) نگه می‌دارد و کدی که ماسک را می‌ساخت ‏(mg, ng) می‌داد، ردیف اول. decoder bitplane خاکستری ماسک را درست به‌شکل (ng, mg) می‌خواند. حلقهٔ جاگذاری الگوها آن را با همان ترتیب عوض‌شدهٔ سازنده می‌خواند، پس دو طرف توافق داشتند و یک بازبینی از صرف منطق جاگذاری آن را می‌پذیرفت. یک تلهٔ نام‌گذاری بدترش کرد: در حلقهٔ جاگذاری متغیری که col نام دارد ردیف‌های گرید را طی می‌کند و Row ستون‌های گرید را

گرید 5 × 3 از الگوهای 4 × 4 روی ناحیهٔ 16 × 8 را در نظر بگیر که v3.539.37 به‌عنوان مورد regression خودش استفاده می‌کند. با HRX = 1024 و HRY = 0، ستون گرید 4 روی x = 16 و ردیف گرید 2 روی y = 8 فرود می‌آید، هر دو بیرون ناحیه. ماسک درست هفت سلول را علامت می‌زند: تمام ستون 4 و تمام ردیف 2. نوشتن‌های عوض‌شده سعی می‌کردند پیکسل‌هایی در اندیس‌های ردیف 3 و 4 در ماسکی که فقط سه ردیف دارد ست کنند، و setter بیت‌مپ آن نوشتن‌های خارج از بازه را بی‌صدا نادیده می‌گرفت. آنچه می‌ماند ستون 2 بود، ردیف‌های 0 تا 2. پس decoder دو سلولی را skip می‌کرد که encoder کدشان کرده بود، و شش سلولی را decode می‌کرد که encoder skip کرده بود

decoder حسابی وقتی این اتفاق می‌افتد شکست نمی‌خورد. پیکسل‌های اضافی را از بیت‌هایی decode می‌کند که مال سلول‌های بعدی‌اند، contextهایش همسایه‌های اشتباه می‌خوانند، و هر اندیس الگو بعد از اولین اختلاف نویز است، و برای همین علامتش یک ناحیهٔ آشفته بود نه چند سلول جابه‌جا. روی گرید مربع همان باگ اغلب نامرئی است: هیچ مختصات عوض‌شده‌ای از ماسک بیرون نمی‌زند، و وقتی سلول‌های بیرون‌ازناحیه نسبت به قطر متقارن‌اند — مثلاً گریدی که به همان تعداد سلول از لبهٔ راست و پایین بیرون می‌زند — ماسک جابه‌جاشده بیت‌به‌بیت همان درست است. ‏HENABLESKIP هم اختیاری است، باید وقتی تصویر خاکستری MMR-کد است 0 باشد، و به‌ندرت توسط encoderها ست می‌شود، پس باگ راه‌های خیلی کمی برای خودنمایی داشت. از v3.539.37 سازنده ‏HSKIP[ng, mg] می‌نویسد و حلقهٔ جاگذاری همان ترتیب را می‌خواند

چرا آفست‌های منفی گرید halftone در سه لایه شکست می‌خورند؟

گریدی از halftone که سمت چپ یا بالای ناحیه‌اش شروع می‌شد PDFlibPas را در سه جای جدا می‌شکست و هر عیب بعدی را پنهان می‌کرد. ‏T.88 این هندسه را عمداً مجاز می‌داند. یک encoder ای که صفحه‌اش را به صفحهٔ برگه هم‌راستا می‌کند نه به ناحیه، یا گرید چرخیده استفاده می‌کند، به‌طور طبیعی گوشه‌های سلول منفی تولید می‌کند که ناحیه آن‌ها را می‌بُرد. ‏v3.539.38 هر سه لایه را با هم فیکس کرد، چون فیکس کردن تک‌تک آن‌ها فقط علامت را عوض می‌کرد

لایهٔ 1: یک فیلد علامت‌دار که بدون علامت خوانده می‌شد

‏T.88 §7.4.5.1.2 ‏HGX و HGY را به‌عنوان مقادیر 32 بیتی علامت‌دار تعریف می‌کند، اما decoder آن‌ها را با همان هلپر 32 بیتی می‌خواند که برای فیلدهای بدون علامت استفاده می‌کرد و آن هلپر هر نتیجهٔ منفی را روی 0 می‌بُرد. گریدی که قرار بود از HGX = -900 شروع شود بی‌سروصدا روی مبدأ ناحیه منتقل می‌شد. در مورد regression و v3.539.38 کل تصویر دو ردیف پایین‌تر بیرون می‌آمد. آن بریدن توضیح می‌دهد چرا دو عیب دیگر این‌قدر دوام آوردند: با مبدأیی که به نامنفی تحمیل شده بود، یک مختصات منفی فقط از طریق گرید چرخیده با HRY > 0 می‌توانست ظاهر شود، جایی که y = HGY + mg × HRX − ng × HRY برای ستون‌های گرید بعدی زیر صفر می‌رود

لایهٔ 2: ‏shr همان >> 8 نیست

‏T.88 می‌نویسد >> 8 و یک shift حسابی می‌خواهد، که به سمت منفی بی‌نهایت گرد می‌کند. decoder آن را به‌شکل shr 8 ترجمه کرده بود. در Delphi و Free Pascal، ‏shr روی یک عدد صحیح علامت‌دار یک shift منطقی است: بیت علامت به‌شکل صفر شیفت می‌شود. برای یک Integer حاوی -512، ‏shr 8 مقدار 16777214 می‌دهد به‌جای -2. الگویی که باید در y = -2 کشیده می‌شد و به نیمهٔ پایینش بریده می‌شد، 16 میلیون ردیف پایین‌تر می‌رفت و به‌عنوان بیرون‌ازناحیه دور انداخته می‌شد. هیچ‌چیز crash نمی‌کرد؛ ردیف بالای halftone کلاً محو می‌شد

لایهٔ 3: مقایسهٔ نقطه‌ثابت به‌جای پیکسل

تست skip مقادیر نقطه‌ثابت را مقایسه می‌کرد نه موقعیت‌های پیکسلی را، و این دو وقتی کسر صفر نیست معادل نیستند. کد اصلی shift منطقی را با آزمودن xx + HPW × 256 <= 0 روی مقدار شیفت‌نشده دور می‌زد، که به‌ظاهر معادل تست T.88 بود. با HGX = -900 و یک الگوی 4 پیکسلی، می‌شود -900 + 1024 = 124، که مثبت است، پس سلول skip نمی‌شود. استاندارد اول شیفت می‌کند: ‏floor(-900 / 256) = -4، و -4 + 4 = 0 شرط x + HPW <= 0 را برقرار می‌کند، پس سلول کلاً بیرون است و باید skip شود. encoder آن را skip می‌کرد، decoder آن را decode می‌کرد، و تصویر خاکستری دقیقاً مثل مورد ماسک جابه‌جاشده انحراف می‌گرفت

مورد regression از v3.539.38 از یک گرید 4 × 3 از الگوهای 4 × 4 با HGX = -900 و HGY = -512 و HRX = 1024 روی ناحیهٔ 12 × 10 استفاده می‌کند. ستون‌های گرید روی x = -4 و 0 و 4 و 8 فرود می‌آیند، پس ستون 0 کلاً بیرون است و جای آن داخل HSKIP است؛ ردیف‌های گرید روی y = -2 و 2 و 6 فرود می‌آیند، پس ردیف 0 باید به دو ردیف پیکسلی پایینیش بریده شود نه دور انداخته شود. فیکس کردن لایه‌ها یکی‌یکی همان پشته را بازتولید می‌کند:

عیب‌های فیکس‌شده	ناحیهٔ decode‌شده
هیچ (قبل از v3.539.38)	گرید به مبدأ کشیده شده، کل تصویر دو ردیف پایین‌تر
فقط خواندن علامت‌دار HGX / HGY	اولین ردیف گرید غایب، بقیه با انحراف تست skip آشفته
خواندن علامت‌دار، shift کفی و تست skip در فضای پیکسل	پیکسل‌به‌پیکسل یکسان با صفحهٔ محاسبه‌شده از T.88 §6.6.5 و با دو decoder مرجع مستقل

فیکس یک هلپر است، ‏HalftoneGridPixel، که سازندهٔ ماسک skip و حلقهٔ جاگذاری مشترک‌اند. مختصات را در Int64 انباشت می‌کند تا حاصل‌ضرب بزرگ mg × HRX سرریز نکند، بر 256 تقسیم می‌کند با گرد شدن به سمت منفی بی‌نهایت، و به ±MaxInt div 2 می‌بَرد تا گرید خراب نتواند بعداً حساب بیت‌مپ را سرریز کند. تست skip حالا آن مقادیر پیکسلی را با HPW و HPH و HBW و HBH مقایسه می‌کند، دقیقاً همان‌طور که §6.6.5.1 می‌گوید

در Delphi چطور یک shift راست حسابی می‌نویسی؟

‏Delphi عملگر shift حسابی ندارد، پس یک shift راست علامت‌دارِ درست باید به‌شکل تقسیم کفی نوشته شود، و div ساده آن تقسیم نیست. ‏div به سمت صفر برش می‌زند. برای مقادیر نامنفی برش و کف توافق دارند، و برای مقادیر منفیِ مضرب دقیق مقسوم‌علیه هم توافق دارند، و برای همین -512 div 256 = -2 در یک تست سریع درست به نظر می‌رسد. در جاهای دیگر اختلاف دارند: ‏-900 div 256 می‌شود -3 در حالی که کف -4 است، و -1 div 256 می‌شود 0 در حالی که کف -1 است. یک مختصات JBIG2 با کسر غیرصفر دقیقاً همان حالتی است که div پیکسل اشتباه می‌دهد

روی کامپایلرهای Win32 و Win64 در Delphi، یک متغیر Integer حاوی -512 که 8 تا به راست شیفت شود 16777214 می‌دهد و یک Int64 حاوی -512 مقدار 72057594037927934. ‏Free Pascal هم shr را shift منطقی تعریف می‌کند و ‏SarLongint و SarInt64 را در یونیت System خودش برای نسخهٔ حسابی فراهم می‌کند، اما آن توابع در Delphi وجود ندارند، پس کد مشترک بین دو کامپایلر به هلپر خودش نیاز دارد:

// تقسیم کفی: برای هر علامتی از A و B به سمت منفی بی‌نهایت گرد می‌کند.
// B نباید 0 باشد، و FloorDiv(Low(Integer), -1) درست مثل 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;

// shift راست حسابی (همان ">>" در 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 هرگز یک عدد منفی را شیفت نمی‌دهد، پس به نحوهٔ برخورد کامپایلر با بیت علامت وابسته نیست و هرگز سرریز نمی‌کند، از جمله برای Low(Integer). هر دو هلپر روی چند میلیون مقدار با یک مرجع کفی 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  shift منطقی، همان باگ قدیمی
  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 داخلی رندر می‌کند، چون رندر پیکسل می‌خواهد. ‏RenderPageToFile و RenderPageToStream هر دو از طریق استریم‌های تصویری JBIG2Decode صفحه به آن می‌رسند، پس رندر دوبارهٔ یک صفحهٔ halftone راه مستقیم تأیید این است که v3.539.38 خروجی‌ات را عوض می‌کند. همان decoder انواع دیگر ناحیهٔ JBIG2 را هم می‌دهد، پوشش داده‌شده در جدول‌های Huffman سفارشی JBIG2 در decoder پاسکال خالص و decode کردن فایل‌های JBIG2 دسترسی‌تصادفی در Delphi، و بیت‌مپ رندرشده تغذیه‌کنندهٔ تبدیل‌هایی مثل رندر کردن صفحات PDF به تک‌رنگ 1 بیتی است

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
      // رندر کردن هر ناحیهٔ JBIG2 را decode می‌کند، halftoneها هم شامل
      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 ساخته‌شده از بایت‌های استریم به تو می‌دهد: هدر فایل، دادهٔ JBIG2Globals و یک سگمنت پایان‌فایل دور دادهٔ صفحه. خاصیت 400 از GetImageListItemIntProperty برای چنین آیتمی 6 گزارش می‌کند. در آن مسیر هیچ چیزی decode نمی‌شود، پس یک .jb2 استخراج‌شده که در viewer دیگر درست به نظر می‌رسد در حالی که صفحهٔ رندرشده نویز نشان می‌داد علامت معمول این دو باگ 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;

وقتی ماسک‌ها یا تبدیل رنگ یک fallback رندرشده را تحمیل می‌کنند، آیتم به‌شکل بیت‌مپ decode‌شده برمی‌گردد و decoder halftone واقعاً کار می‌کند. بیشتر دربارهٔ لیست تصاویر در استخراج متن و تصویر و فونت PDF در Delphi

مرجع سریع: قواعد گرید halftone در JBIG2

• ماسک skip را به‌شکل HSKIP[ng, mg] اندیس‌گذاری کن، ستون گرید اول، و هر جا سلولی جاگذاری می‌شود با همان ترتیب برگردانش (T.88 §6.6.5.1، فیکس در PDFlibPas v3.539.37)
• هر کد halftone یا گرید را با یک گرید نامربع و مجموعه‌ای نامتقارن از سلول‌های بیرون‌ازناحیه تست کن، چون گرید مربع می‌تواند یک اندیس جابه‌جاشده را کامل پنهان کند
• ‏HGX و HGY را به‌عنوان مقادیر 32 بیتی علامت‌دار بخوان (T.88 §7.4.5.1.2)، هرگز از طریق هلپری بدون علامت که منفی‌ها را می‌بُرد نه
• ‏>> 8 استاندارد را به‌شکل تقسیم کفی بر 256 ترجمه کن، نه به‌شکل shr 8 و نه به‌شکل div 256
• تست skip را روی موقعیت‌های پیکسلی شیفت‌شده اجرا کن؛ فرم نقطه‌ثابت هر وقت کسر صفر نباشد فرق می‌کند، همان‌طور که HGX = -900 با یک الگوی 4 پیکسلی نشان می‌دهد
• مختصات گرید را در Int64 انباشت کن و قبل از دادن به کد بیت‌مپ ببَر، تا گرید خراب نتواند سرریز کند
• اگر سندهایت ناحیه‌های halftone با HENABLESKIP یا مبدأهای منفی گرید یا گریدهای چرخیده دارند، به v3.539.38 یا بعدتر ارتقا بده

‏PDFlibPas اسناد PDF را از Delphi و C++Builder با یک decoder بومی پاسکالِ JBIG2 رندر و استخراج و ویرایش می‌کند که حالا ماسک‌های skip halftone و مبدأهای منفی گرید و گریدهای چرخیده را همان‌طور که T.88 مشخص می‌کند می‌دهد. برای قابلیت‌ها و ویرایش‌ها و دانلود نسخهٔ آزمایشی ‏PDFlibPas Delphi PDF library را ببین