{ DOS-text
Реализация базовых функций словаря для сжатия Лемпеля-Зива

   1) FindNodeInBinaryTree - поиск узла в упорядоченном бинарном дереве.

   2) AddNodeToBinaryTree - добавление узла в упорядоченное идеально
			    балансированное бинарное дерево с сохранением
			    балансировки.

   2a) AddNodeForDecode - добавление узла в словарь для декодировки,
			  при этом создание двоичного упорядоченного
			  идеально балансированного дерева не
			  производится.

   3) DecodeNode - декодирование номера (кода) узла словаря в
		   последовательность байт.

   4) FindFragmentInDictionary -  поиск фрагмента в словаре.
}
{---------------------------------------------------------------------------
(c) Copyright	 Aleksandrov O.E., 2000

   Molecular Physics department, USTU, Ekaterinsburg, K-2, 620002, RUSSIA
   phone 75-47-15
   E-mail: aleks@dpt.ustu.ru

(c) Copyright Александров О.Е., 2000

   620002, Екатеринбург, К-2, УГТУ, Кафедра молекулярной физики
   тел. 75-47-15
   E-mail: aleks@dpt.ustu.ru
----------------------------------------------------------------------------}

{ Win-text
╨хрышчрЎш  срчют√ї ЇєэъЎшщ ёыютрЁ  фы  ёцрЄш  ╦хьяхы -╟штр

   1) FindNodeInBinaryTree - яюшёъ єчыр т єяюЁ фюўхээюь сшэрЁэюь фхЁхтх.

   2) AddNodeToBinaryTree - фюсртыхэшх єчыр т єяюЁ фюўхээюх шфхры№эю
			    срырэёшЁютрээюх сшэрЁэюх фхЁхтю ё ёюїЁрэхэшхь
			    срырэёшЁютъш.

   2a) AddNodeForDecode - фюсртыхэшх єчыр т ёыютрЁ№ фы  фхъюфшЁютъш,
			  яЁш ¤Єюь ёючфрэшх фтюшўэюую єяюЁ фюўхээюую
			  шфхры№эю срырэёшЁютрээюую фхЁхтр эх
			  яЁюшчтюфшЄё .

   3) DecodeNode - фхъюфшЁютрэшх эюьхЁр (ъюфр) єчыр ёыютрЁ  т
		   яюёыхфютрЄхы№эюёЄ№ срщЄ.

   4) FindFragmentInDictionary -  яюшёъ ЇЁруьхэЄр т ёыютрЁх.
}
{---------------------------------------------------------------------------
(c) Copyright	 Aleksandrov O.E., 2000

   Molecular Physics department, USTU, Ekaterinsburg, K-2, 620002, RUSSIA
   phone 75-47-15
   E-mail: aleks@dpt.ustu.ru

(c) Copyright └ыхъёрэфЁют ╬.┼., 2000

   620002, ┼ърЄхЁшэсєЁу, ╩-2, ╙├╥╙, ╩рЇхфЁр ьюыхъєы Ёэющ Їшчшъш
   Єхы. 75-47-15
   E-mail: aleks@dpt.ustu.ru
----------------------------------------------------------------------------}
Unit LZBase;
{$X+}
{$IfDef NoChecking}
  {$R-,S-,Q-}
{$EndIf Def NoChecking}

INTERFACE
  USES {$IfDef Debug}LZTests,{$EndIf}ComTypes, LZTypes;
{ Далее будут различаться термины:
    "Корень дерева" (Root) и "корневой узел дерева" (RootNode).

"Корень дерева" (Root) - означает узел для которого дерево является
			 продолжением, он не принадлежит дереву, а
			 является его предшествующим узлом.

"Корневой узел дерева" (RootNode) - означает узел являющийся корневым узлом
				    дерева, он принадлежит дереву.

"Корень дерева (ссылка)" (RootRef) - означает ячейку памяти в которой
				     находится ссылка на "корневой узел
				     дерева".

Узел идентифицируется по номеру (Index) в массиве узлов.
}
{ ─рыхх сєфєЄ ЁрчышўрЄ№ё  ЄхЁьшэ√:
    "╩юЁхэ№ фхЁхтр" (Root) ш "ъюЁэхтющ єчхы фхЁхтр" (RootNode).

"╩юЁхэ№ фхЁхтр" (Root) - ючэрўрхЄ єчхы фы  ъюЄюЁюую фхЁхтю  ты хЄё 
			 яЁюфюыцхэшхь, юэ эх яЁшэрфыхцшЄ фхЁхтє, р
			  ты хЄё  хую яЁхф°хёЄтє■∙шь єчыюь.

"╩юЁэхтющ єчхы фхЁхтр" (RootNode) - ючэрўрхЄ єчхы  ты ■∙шщё  ъюЁэхт√ь єчыюь
				    фхЁхтр, юэ яЁшэрфыхцшЄ фхЁхтє.

"╩юЁхэ№ фхЁхтр (ёё√ыър)" (RootRef) - ючэрўрхЄ  ўхщъє ярь Єш т ъюЄюЁющ
				     эрїюфшЄё  ёё√ыър эр "ъюЁэхтющ єчхы
				     фхЁхтр".

╙чхы шфхэЄшЇшЎшЁєхЄё  яю эюьхЁє (Index) т ьрёёштх єчыют.
}

{ 1. Поиск узла в упорядоченном бинарном дереве }
{ 1. ╧юшёъ єчыр т єяюЁ фюўхээюь сшэрЁэюь фхЁхтх }
function FindNodeInBinaryTree(
	   aByte:tByte;           { байт для поиска } { срщЄ фы  яюшёър }
	   aRootNodeIndex:tIndex; { номер корневого узла для дерева } { эюьхЁ ъюЁэхтюую єчыр фы  фхЁхтр, т ъюЄюЁюь т√яюыэ хЄё  яюшёъ }
     const Dic:tDictionary        { словарь } { ёыютрЁ№, юяшёрэшх ёь. LZTypes }
):tIndex; {$IfDef Delphi} register; {$EndIf}
{ ВОЗВРАЩАЕТ:
  номер узла с байтом AByte для дерева с корневым узлом ARootNodeIndex,
  иначе cNilNode, если байт не найден. }
{ ┬╬╟┬╨└┘└┼╥:
  эюьхЁ єчыр ё срщЄюь AByte фы  фхЁхтр ё ъюЁэхт√ь єчыюь ARootNodeIndex,
  шэрўх cNilNode, хёыш срщЄ эх эрщфхэ. }

{ 2. Добавление узла в упорядоченное идеально балансированное бинарное дерево }
{ 2. ─юсртыхэшх єчыр т єяюЁ фюўхээюх шфхры№эю срырэёшЁютрээюх сшэрЁэюх фхЁхтю }
function AddNodeToBinaryTree(
	  AByte:byte;        { байт для вставки } { срщЄ фы  тёЄртъш }
	  ARootIndex:tIndex; { корень дерева } { ъюЁхэ№ фхЁхтр }
      var Dic:tDictionary    { словарь } { ёыютрЁ№ }
):tNodeIndex; {$IfDef Delphi} register; {$EndIf}
{ ВОЗВРАЩАЕТ:
   номер вставленного узла,
   иначе cNilIndex - нет свободного места в словаре }
{ ┬╬╟┬╨└┘└┼╥:
   эюьхЁ тёЄртыхээюую єчыр,
   шэрўх cNilIndex - эхЄ ётюсюфэюую ьхёЄр т ёыютрЁх }

{ 2x. Добавление узла к словарю при декодировании
Примечание. При декодировке восстанавливать двоичное дерево нет
необходимости, поскольку используется только массив Predecessors.
Это значительно ускоряет процесс декодирования (в 2-3 раза по сравнению с
процессом кодирования).
Усовершенствование включается директивой условной компиляции "$DEFINE Fast1". }
{ 2x. ─юсртыхэшх єчыр ъ ёыютрЁ■ яЁш фхъюфшЁютрэшш
╧Ёшьхўрэшх. ╧Ёш фхъюфшЁютъх тюёёЄрэртыштрЄ№ фтюшўэюх фхЁхтю эхЄ
эхюсїюфшьюёЄш, яюёъюы№ъє шёяюы№чєхЄё  Єюы№ъю ьрёёшт Predecessors.
▌Єю чэрўшЄхы№эю єёъюЁ хЄ яЁюЎхёё фхъюфшЁютрэш  (т 2-3 Ёрчр яю ёЁртэхэш■ ё
яЁюЎхёёюь ъюфшЁютрэш ).
╙ёютхЁ°хэёЄтютрэшх тъы■ўрхЄё  фшЁхъЄштющ єёыютэющ ъюьяшы Ўшш "$DEFINE Fast1". }
function AddNodeForDecode(
	  AByte:byte;        { байт для вставки } { срщЄ фы  тёЄртъш }
	  ARootIndex:tIndex; { корень дерева } { ъюЁхэ№ фхЁхтр }
      var Dic:tDictionary    { словарь } { ёыютрЁ№ }
):tNodeIndex; {$IfDef Delphi} register; {$EndIf}
{ ВОЗВРАЩАЕТ:
   номер вставленного узла,
   иначе cNilIndex - нет свободного места в словаре }
{ ┬╬╟┬╨└┘└┼╥:
   эюьхЁ тёЄртыхээюую єчыр,
   шэрўх cNilIndex - эхЄ ётюсюфэюую ьхёЄр т ёыютрЁх }

{ 3. Декодирование узла словаря в последовательность байт }
{ 3. ─хъюфшЁютрэшх єчыр ёыютрЁ  т яюёыхфютрЄхы№эюёЄ№ срщЄ }
function DecodeNode(
	   ANodeIndex:tNodeIndex; { начальный узел } { эрўры№э√щ єчхы }
       var ABuffer;                  { буфер для декодированных данных } { сєЇхЁ фы  фхъюфшЁютрээ√ї фрээ√ї }
	   ABufferSize:tBufferIndex; { размер буфера } { ЁрчьхЁ сєЇхЁр }
     const Dic:tDictionary           { словарь } { ёыютрЁ№ }
):tSignedBufferIndex; {$IfDef Delphi} register; {$EndIf}
{ ┬╬╟┬╨└┘└┼╥:
   >=0, хёыш фхъюфшЁютрэю фю ъюэЎр,
   <0 - ЁрчьхЁ эхфюёЄр■∙хую ьхёЄр т сєЇхЁх }

{ 4. Проход фрагмента в словаре }
{ 4. ╧Ёюїюф ЇЁруьхэЄр т ёыютрЁх }
function FindFragmentInDictionary(
	   const ABuffer; { буфер с данными (байтами) для поиска в словаре }
                          { сєЇхЁ ё фрээ√ьш (срщЄрьш) ЇЁруьхэЄр фы  яюшёър хую т ёыютрЁх }
		 ABufferSize:tBufferIndex; { размер буфера } { ЁрчьхЁ сєЇхЁр }
	   var   ARootIndex:tIndex; { ВХОД: номер корня для дерева,
					    откуда начинать поиск
					    (текущий фрагмент)
				     ВЫХОД: последний найденный узел
					    (не изменяется, если ничего
					    не найдено)}
                                    { ┬╒╬─: эюьхЁ ъюЁэ  фы  фхЁхтр,
					    юЄъєфр эрўшэрЄ№ яюшёъ
					    (Єхъє∙шщ ЇЁруьхэЄ)
				     ┬█╒╬─: яюёыхфэшщ эрщфхээ√щ єчхы
					    (эх шчьхэ хЄё , хёыш эшўхую
					    эх эрщфхэю)}
	   const Dic:tDictionary    { словарь } { ёыютрЁ№ }
):tBufferIndex; {$IfDef Delphi} register; {$EndIf}
{ ВОЗВРАЩАЕТ: 1) размер фрагмента, найденного в буфере и
  2) номер последнего узла фрагмента в ARootIndex }
{ ┬╬╟┬╨└┘└┼╥:
  1) ЁрчьхЁ ЇЁруьхэЄр шч ABuffer, эрщфхээюую т ёыютрЁх;
  2) ARootIndex = эюьхЁ яюёыхфэхую єчыр ЇЁруьхэЄр }

IMPLEMENTATION

{ 1. Поиск узла в упорядоченном бинарном дереве }
{ 1. ╧юшёъ єчыр т єяюЁ фюўхээюь сшэрЁэюь фхЁхтх }
function FindNodeInBinaryTree(
	   aByte:tByte;           { байт для поиска } { срщЄ фы  яюшёър }
	   aRootNodeIndex:tIndex; { номер корневого узла для дерева }
                                  { эюьхЁ ъюЁэхтюую єчыр фы  фхЁхтр }
     const Dic:tDictionary        { словарь } { ёыютрЁ№ }
):tIndex;
{ ВОЗВРАЩАЕТ:
  номер узла с байтом AByte для дерева с корнем ARootNodeIndex,
  иначе cNilNode, если байт не найден. }
{ ┬╬╟┬╨└┘└┼╥:
  эюьхЁ єчыр ё срщЄюь AByte фы  фхЁхтр ё ъюЁэхь ARootNodeIndex,
  шэрўх cNilNode, хёыш срщЄ эх эрщфхэ. }

{$IfNDef ASM}
  var PNodes:tPNodesArray; b:tByte; PBytes:tPBytesArray;
begin
  { Поиск с барьером. Отслеживается ОДНО событие:
      1) элемент найден (Dic.Bytes^[ARootNodeIndex]=AByte) - вернуть ARootNodeIndex.
  Поскольку для cNilIndex определен элемент в массиве Dic.Nodes,
  и одновременно ссылка на этот элемент является признаком конца поиска
  по событию "нет больше элементов в дереве", то можно уменьшить число
  операций сравнения при поиске, создав "барьер" в Dic.Bytes^[cNilIndex].
  На Dic.Bytes^[cNilIndex] ссылаются ВСЕ "пустые ссылки", поместив в этот
  элемент значение AByte, мы можем ограничиться проверкой
      Dic.Bytes^[ARootNodeIndex]=AByte
  с гарантией, что это равенство выполнится в ЛЮБОМ случае при поиске по
  дереву. Это произойдет либо в случае присутствия AByte в дереве, либо при
  достижении любой пустой ссылки (ARootNodeIndex=cNilIndex). В обоих случаях
  произойдет правильный возврат значения: индекс элемента, если AByte есть в
  дереве, или cNilIndex если его там нет.
  }
  { ╧юшёъ ё срЁ№хЁюь. ╬ЄёыхцштрхЄё  ╬─═╬ ёюс√Єшх:
      1) ¤ыхьхэЄ эрщфхэ (Dic.Bytes^[ARootNodeIndex]=AByte) - тхЁэєЄ№ ARootNodeIndex.
  ╧юёъюы№ъє фы  cNilIndex юяЁхфхыхэ ¤ыхьхэЄ т ьрёёштх Dic.Nodes,
  ш юфэютЁхьхээю ёё√ыър эр ¤ЄюЄ ¤ыхьхэЄ  ты хЄё  яЁшчэръюь ъюэЎр яюшёър
  яю ёюс√Єш■ "эхЄ сюы№°х ¤ыхьхэЄют т фхЁхтх", Єю ьюцэю єьхэ№°шЄ№ ўшёыю
  юяхЁрЎшщ ёЁртэхэш  яЁш яюшёъх, ёючфрт "срЁ№хЁ" т Dic.Bytes^[cNilIndex].
  ═р Dic.Bytes^[cNilIndex] ёё√ыр■Єё  ┬╤┼ "яєёЄ√х ёё√ыъш", яюьхёЄшт т ¤ЄюЄ
  ¤ыхьхэЄ чэрўхэшх AByte, ь√ ьюцхь юуЁрэшўшЄ№ё  яЁютхЁъющ
      Dic.Bytes^[ARootNodeIndex]=AByte
  ё урЁрэЄшхщ, ўЄю ¤Єю ЁртхэёЄтю т√яюыэшЄё  т ╦▐┴╬╠ ёыєўрх яЁш яюшёъх яю
  фхЁхтє. ▌Єю яЁюшчющфхЄ ышсю т ёыєўрх яЁшёєЄёЄтш  AByte т фхЁхтх, ышсю яЁш
  фюёЄшцхэшш ы■сющ яєёЄющ ёё√ыъш (ARootNodeIndex=cNilIndex). ┬ юсюшї ёыєўр ї
  яЁюшчющфхЄ яЁртшы№э√щ тючтЁрЄ чэрўхэш : шэфхъё ¤ыхьхэЄр, хёыш AByte хёЄ№ т
  фхЁхтх, шыш cNilIndex хёыш хую Єрь эхЄ.
  }
  { инициализация вспомогательных переменных }
  { шэшЎшрышчрЎш  тёяюьюурЄхы№э√ї яхЁхьхээ√ї }
  PNodes:=Dic.Nodes;
  PBytes:=Dic.Bytes;

  { установка барьера } { єёЄрэютър срЁ№хЁр }
  PBytes^[cNilIndex]:=AByte;

  { поиск } { яюшёъ }
  b:=PBytes^[aRootNodeIndex];
  while b<>aByte do begin
    aRootNodeIndex:=PNodes^[aRootNodeIndex].LeftRight[aByte>b];
    b:=PBytes^[aRootNodeIndex];
  end;

  { возвращаем значение индекса для найденного элемента }
  { тючтЁр∙рхь чэрўхэшх шэфхъёр фы  эрщфхээюую ¤ыхьхэЄр }
  FindNodeInBinaryTree:=aRootNodeIndex;
end;

{$Else IfNDef ASM}
{ то же самое, но на ассемблере }{ Єю цх ёрьюх, эю эр рёёхьсыхЁх - яЁръЄшўхёъш эхЄ ¤ЇЇхъЄр яю ёъюЁюёЄш ЁрсюЄ√ }
  {$IfNDef Delphi}
assembler;
  asm
    mov dx,ds
      { DS:SI -> Dic }
      lds si,Dic
      { инициализация указателей
       ES:DI -> Dic.Bytes^
       DS:SI -> Dic.Nodes^ }
      les di,tDictionary([si]).Bytes
      lds si,tDictionary([si]).Nodes
      { AL:= AByte}
      mov al,AByte
      { установка барьера: PBytes^[cNilIndex]:=AByte;}
      mov es:[di],al
      { BX:= ARootNodeIndex}
      mov bx,ARootNodeIndex
      @Loop:
	{ сравниваем AByte с байтом текущего узла }
	cmp es:[di][bx],al; je @EndLoop { байт найден - выходим }
	  rcl bx,2; mov bx,tIndex(tNode([si][bx]).LeftRight)
      jmp @Loop
      @EndLoop:
      { AX:= номер найденного узла }
      mov ax,bx
    mov ds,dx
  end;
  {$Else}
   register;
  { EAX=AByte - срщЄ фы  яюшёър
    EDX=ARootNodeIndex - эюьхЁ ъюЁэхтюую єчыр фы  фхЁхтр
    ECX->Dic  - ёыютрЁ№ }
  asm
    push ebx
      { шэшЎшрышчрЎш  єърчрЄхыхщ
       EBX -> Dic.Nodes^
       ECX -> Dic.Bytes^ }
      mov ebx,tDictionary.Nodes([Dic])
      mov ecx,tDictionary.Bytes([Dic])
      { єёЄрэютър срЁ№хЁр: PBytes^[cNilIndex]:=AByte; }
      mov [ecx],AByte
      { яюшёъ }
      @Loop:
	cmp [ecx][ARootNodeIndex],AByte; je @EndLoop
	{ ARootNodeIndex = ARootNodeIndex*8+CF*4}
	rcl ARootNodeIndex,3
	{ ARootNodeIndex:= Dic.Nodes^[ARootNodeIndex].LeftRight[AByte > Bytes^[ARootNodeIndex] }
	mov ARootNodeIndex,tIndex(tNode.LeftRight([ebx][ARootNodeIndex]))
      jmp @Loop
      @EndLoop:
      { тючтЁр∙рхь чэрўхэшх шэфхъёр фы  эрщфхээюую ¤ыхьхэЄр }
      mov eax,ARootNodeIndex
    pop ebx
  end;
  {$EndIf}
{$EndIf NDef ASM}

function AllocateNode(var Dic:tDictionary; PrevNode:tIndex):tIndex; forward;
procedure AddNode(ANodeIndex:tIndex; ARootRef:tPIndex; var Dic:tDictionary); forward;

{ 2. Добавление узла в упорядоченное идеально балансированное бинарное дерево }
{ 2. ─юсртыхэшх єчыр т єяюЁ фюўхээюх шфхры№эю срырэёшЁютрээюх сшэрЁэюх фхЁхтю }
function AddNodeToBinaryTree(
	  AByte:byte;        { байт для вставки }{ срщЄ фы  тёЄртъш }
	  ARootIndex:tIndex; { корень дерева }{ ъюЁхэ№ фхЁхтр }
      var Dic:tDictionary    { словарь }{ ёыютрЁ№ }
):tNodeIndex;
{ ВОЗВРАЩАЕТ:
   номер вставленного узла,
   иначе cNilIndex - нет свободного места в словаре }
{ ┬╬╟┬╨└┘└┼╥:
   эюьхЁ тёЄртыхээюую єчыр,
   шэрўх cNilIndex - эхЄ ётюсюфэюую ьхёЄр т ёыютрЁх }

  var NewNodeIndex:tNodeIndex;
begin
  { получить свободный узел } { яюыєўшЄ№ ётюсюфэ√щ єчхы }
  NewNodeIndex:=AllocateNode(Dic, ARootIndex);
  { вернуть его номер в качестве результата выполнения функции }
  { тхЁэєЄ№ хую эюьхЁ т ърўхёЄтх Ёхчєы№ЄрЄр т√яюыэхэш  ЇєэъЎшш }
  AddNodeToBinaryTree:=NewNodeIndex;
  { если свободный узел получен } { хёыш ётюсюфэ√щ єчхы яюыєўхэ }
  if NewNodeIndex<>cNilIndex then begin
    { записать в него данные } { чряшёрЄ№ т эхую фрээ√х }
    Dic.Bytes^[NewNodeIndex]:=AByte;
    { и добавить узел в дерево } { ш фюсртшЄ№ єчхы т фхЁхтю }
    AddNode(NewNodeIndex, @Dic.Successors^[ARootIndex], Dic);
    {$IfDef Debug} {$IfOpt R+}
    { доп. проверка сбалансированности для целей отладки }
    { фюя. яЁютхЁър ёсрырэёшЁютрээюёЄш фы  Ўхыхщ юЄырфъш }
    if not CheckNodeBalance(Dic, ARootIndex) then begin
      CheckNodeBalance(Dic, ARootIndex);
      RunError(201);
    end;
    {$EndIf} {$EndIf}
  end;
end;

{ 2x. ─юсртыхэшх єчыр ─╦▀ фхъюфшЁютъш яЁш ═┼╧╬╦═╬╠ тюёёЄрэютыхэшш ёыютрЁ  }
function AddNodeForDecode(
	  AByte:byte;        { байт для вставки }{ срщЄ фы  тёЄртъш }
	  ARootIndex:tIndex; { корень дерева }{ ъюЁхэ№ фхЁхтр }
      var Dic:tDictionary    { словарь }{ ёыютрЁ№ }
):tNodeIndex;
  var NewNodeIndex:tNodeIndex;
begin
  if Dic.Descriptors.Max=Dic.Descriptors.FirstFree then begin
    { свободных узлов нет } { ётюсюфэ√ї єчыют эхЄ }
    AddNodeForDecode:=cNilIndex;
  end else begin
  { свободные узлы есть } { ётюсюфэ√х єчы√ хёЄ№ }

    { возвращаем его индекс } { тючтЁр∙рхь хую шэфхъё }
    NewNodeIndex:=Dic.Descriptors.FirstFree;

    { помечаем первый свободный узел как занятый }
    { яюьхўрхь яхЁт√щ ётюсюфэ√щ єчхы ъръ чрэ Є√щ }
    Inc(Dic.Descriptors.FirstFree);

    { заполняем данные узла } { чряюыэ хь фрээ√х єчыр }
    Dic.Predecessors^[NewNodeIndex]:=ARootIndex;
    Dic.Bytes^[NewNodeIndex]:=AByte;

    { возвращаем его } { тючтЁр∙рхь хую }
    AddNodeForDecode:=NewNodeIndex;
  end;
end;


{ Размещение нового узла из числа свободных }
{ ╨рчьх∙хэшх эютюую єчыр шч ўшёыр ётюсюфэ√ї }
function AllocateNode(var Dic:tDictionary; PrevNode:tIndex):tIndex;
  var NewNodeIndex:tIndex;
begin
  if Dic.Descriptors.Max=Dic.Descriptors.FirstFree then begin
    { свободных узлов нет } { ётюсюфэ√ї єчыют эхЄ }
    AllocateNode:=cNilIndex;
  end else begin
    { свободные узлы есть } { ётюсюфэ√х єчы√ хёЄ№ }
    { помечаем первый свободный узел как занятый }
    { яюьхўрхь яхЁт√щ ётюсюфэ√щ єчхы ъръ чрэ Є√щ }
    Inc(Dic.Descriptors.FirstFree);
    { возвращаем его индекс } { тючтЁр∙рхь хую шэфхъё }
    NewNodeIndex:=Pred(Dic.Descriptors.FirstFree);

    { заполняем данные узла } { чряюыэ хь фрээ√х єчыр }
    Dic.Nodes^[NewNodeIndex]:=cNullNode;
    Dic.Flags^[NewNodeIndex]:=[];
    {$IfNDef Fast1}
    Dic.Predecessors^[NewNodeIndex]:=PrevNode;
    {$EndIf Fast1}
    Dic.Successors^[NewNodeIndex]:=cNilIndex;

    { возвращаем его } { тючтЁр∙рхь хую }
    AllocateNode:=NewNodeIndex;
  end;
end;

{ 3. Декодирование узла словаря в последовательность байт }
{ 3. ─хъюфшЁютрэшх єчыр ёыютрЁ  т яюёыхфютрЄхы№эюёЄ№ срщЄ }
function DecodeNode(
	   ANodeIndex:tNodeIndex; { начальный узел }{ эрўры№э√щ єчхы (яЁртшы№эхх ёърчрЄ№ яюёыхфэшщ єчхы ЇЁруьхэЄр)}
       var ABuffer;                  { буфер для декодированных данных }
				     { сєЇхЁ фы  фхъюфшЁютрээ√ї фрээ√ї }
	   ABufferSize:tBufferIndex; { размер буфера }{ ЁрчьхЁ сєЇхЁр }
     const Dic:tDictionary           { словарь } { ёыютрЁ№ }
):tSignedBufferIndex;
{ ВОЗВРАЩАЕТ:
   0, если декодировано до конца,
   иначе - размер недостающего места в буфере }
{ ┬╬╟┬╨└┘└┼╥:
   0, хёыш фхъюфшЁютрэю фю ъюэЎр,
   шэрўх - ЁрчьхЁ эхфюёЄр■∙хую ьхёЄр т сєЇхЁх }
{$IfNDef ASM}
  var
    i:tBufferIndex;
    PBytes:tPBytesArray;
    PPredecessors:tPLineReferenciesArray;
begin
  {$IfOpt R+}
  if (ANodeIndex<=cCode_NewByte) then begin
    RunError(201);
  end;
  if (ANodeIndex>=Dic.Indexes.FirstFree) then begin
    RunError(201);
  end;
  {$EndIf}
  { Инициализируем локальные указатели на данные дерева - это для ускорения работы }
  { ╚эшЎшрышчшЁєхь ыюъры№э√х єърчрЄхыш эр фрээ√х фхЁхтр - ¤Єю фы  єёъюЁхэш  ЁрсюЄ√ }
  PBytes:=Dic.Bytes;
  PPredecessors:=Dic.Predecessors;
  { Декодируем, но в буфер символы попадают в обратном порядке  }
  { ─хъюфшЁєхь, эю т сєЇхЁ ёшьтюы√ яюярфр■Є т юсЁрЄэюь яюЁ фъх  }
  i:=ABufferSize;
  { пока не кончился фрагмент и в буфере есть свободное место  }
  { яюър эх ъюэўшыё  ЇЁруьхэЄ ш т сєЇхЁх хёЄ№ ётюсюфэюх ьхёЄю  }
  while (ANodeIndex>cRootIndex) and (i>0) do begin
    { изменяем номер свободного байта в буфере}
    { шчьхэ хь эюьхЁ ётюсюфэюую срщЄр т сєЇхЁх}
    Dec(i);
    { помещаем в свободный байт буфера очередной байт фрагмента }
    { яюьх∙рхь т ётюсюфэ√щ срщЄ сєЇхЁр юўхЁхфэющ срщЄ ЇЁруьхэЄр }
    tBuffer(ABuffer)[i]:=PBytes^[ANodeIndex];
    { устанавливаем номер очередного узла фрагмента }
    { єёЄрэртыштрхь эюьхЁ юўхЁхфэюую єчыр ЇЁруьхэЄр }
    ANodeIndex:=PPredecessors^[ANodeIndex];
  end;
  if (ANodeIndex<=cRootIndex) then begin
  { декодировали успешно }
  { фхъюфшЁютрыш єёях°эю }
    if i>0 then Move(tBuffer(ABuffer)[i],tBuffer(ABuffer)[0],ABufferSize-i);
    DecodeNode:=ABufferSize-i;
    { инвертируем порядок символов в буфере  }
    { шэтхЁЄшЁєхь яюЁ фюъ ёшьтюыют т сєЇхЁх  }
  end else begin
  { НЕдекодировали - недостаточно места в буфере }
  { ═┼фхъюфшЁютрыш - эхфюёЄрЄюўэю ьхёЄр т сєЇхЁх }
    { считаем, сколько не хватает } { ёўшЄрхь, ёъюы№ъю эх їтрЄрхЄ }
    i:=0;
    repeat
      Inc(i);
      ANodeIndex:=PPredecessors^[ANodeIndex];
    until (ANodeIndex=cRootIndex);
    DecodeNode:=-i;
  end;
end;
(*
  var
    i,j:tBufferIndex;
    b:tByte;
    PBytes:tPBytesArray;
    PPredecessors:tPLineReferenciesArray;
begin
  {$IfOpt R+}
  if (ANodeIndex<=cCode_NewByte) then begin
    RunError(201);
  end;
  if (ANodeIndex>=Dic.Indexes.FirstFree) then begin
    RunError(201);
  end;
  {$EndIf}
  { Инициализируем локальные указатели на данные дерева - это для ускорения работы }
  { ╚эшЎшрышчшЁєхь ыюъры№э√х єърчрЄхыш эр фрээ√х фхЁхтр - ¤Єю фы  єёъюЁхэш  ЁрсюЄ√ }
  PBytes:=Dic.Bytes;
  PPredecessors:=Dic.Predecessors;
  { Декодируем, но в буфер символы попадают в обратном порядке  }
  { ─хъюфшЁєхь, эю т сєЇхЁ ёшьтюы√ яюярфр■Є т юсЁрЄэюь яюЁ фъх  }
  i:=0;
  { пока не кончился фрагмент и в буфере есть свободное место  }
  { яюър эх ъюэўшыё  ЇЁруьхэЄ ш т сєЇхЁх хёЄ№ ётюсюфэюх ьхёЄю  }
  while (ANodeIndex>cRootIndex) and (i<ABufferSize) do begin
    { помещаем в свободный байт буфера очередной байт фрагмента }
    { яюьх∙рхь т ётюсюфэ√щ срщЄ сєЇхЁр юўхЁхфэющ срщЄ ЇЁруьхэЄр }
    tBuffer(ABuffer)[i]:=PBytes^[ANodeIndex];
    { изменяем номер свободного байта в буфере}
    { шчьхэ хь эюьхЁ ётюсюфэюую срщЄр т сєЇхЁх}
    Inc(i);
    { устанавливаем номер очередного узла фрагмента }
    { єёЄрэртыштрхь эюьхЁ юўхЁхфэюую єчыр ЇЁруьхэЄр }
    ANodeIndex:=PPredecessors^[ANodeIndex];
  end;
  if (ANodeIndex<=cRootIndex) then begin
  { декодировали успешно }
  { фхъюфшЁютрыш єёях°эю }
    DecodeNode:=i;
    { инвертируем порядок символов в буфере  }
    { шэтхЁЄшЁєхь яюЁ фюъ ёшьтюыют т сєЇхЁх  }
    Dec(i); j:=0;
    while (j<i) do begin
      b:=tBuffer(ABuffer)[i];
      tBuffer(ABuffer)[i]:=tBuffer(ABuffer)[j];
      tBuffer(ABuffer)[j]:=b;
      Dec(i); Inc(j);
    end;
  end else begin
  { НЕдекодировали - недостаточно места в буфере }
  { ═┼фхъюфшЁютрыш - эхфюёЄрЄюўэю ьхёЄр т сєЇхЁх }
    { считаем, сколько не хватает } { ёўшЄрхь, ёъюы№ъю эх їтрЄрхЄ }
    i:=0;
    repeat
      Inc(i);
      ANodeIndex:=PPredecessors^[ANodeIndex];
    until (ANodeIndex=cRootIndex);
    DecodeNode:=-i;
  end;
end;
*)
{$Else IfNDef ASM}
  {$IfNDef Delphi}
var
  PBytes:tPBytesArray;
  PPredecessors:tPLineReferenciesArray;
begin
  {$IfOpt R+}
  if (ANodeIndex<=cCode_NewByte) then begin
    RunError(201);
  end;
  if (ANodeIndex>=Dic.Descriptors.FirstFree) then begin
    RunError(201);
  end;
 {$EndIf}
  PBytes:=Dic.Bytes;
  PPredecessors:=Dic.Predecessors;
  asm
  { декодируем, но!!! в буфер символы попадают в обратном порядке  }
    mov dx,ds
    les di,ABuffer { ES:[DI]->ABuffer[0]}
    mov ax,di
    mov bx,ANodeIndex { BX:=ANodeIndex }
    mov cx,ABufferSize { CX:=ABufferSize }
    mov word(@Result)[2],0;
    cld

    { while BX>cRootIndex do }
    cmp bx,cRootIndex; jbe @OkDecode
    jcxz @FailDecode { if CX=0 then goto @FailDecode }
    @Loop:
      { ABuffer[DI]:=PBytes^[BX] }
      lds si,PBytes; add si,bx; movsb
      { BX:=PPredecessors^[BX] }
      lds si,PPredecessors; shl bx,1;  mov bx,tIndex([si][bx])
      cmp bx,cRootIndex
    loopnz @Loop { CX:=XC-1; if (CX<>0) and (BX<>cRootIndex) then goto @Loop }

    { проверка полной декодировки }
    jbe @OkDecode

    @FailDecode: { НЕдекодировали - недостаточно места в буфере }
      { считаем, сколько не хватает }
      lds si,PPredecessors
      mov ax,cRootIndex
      @LoopCount: { repeat }
	inc cx
	{ BX:=PPredecessors^[BX] }
	shl bx,1; mov bx,tIndex([si][bx])
	cmp bx,ax
      ja @LoopCount { until BX=cRootIndex }
      mov word(@Result),0 { DecodeNode:= -нехватка размера буфера }
      sub word(@Result),cx; sbb word(@Result)[2],0
    jmp @End

    @OkDecode: { декодировано все }
      mov cx,di; sub cx,ax { CX:= число декодированных байт }
      mov word(@Result),cx { DecodeNode:=CX }
      shr cx,1 { CX:=CX div 2 }
      jcxz @SkipInvert { if CX=0 then goto @SkipInvert }
	{ инвертируем }
	lds si,ABuffer { DS:[si]->ABuffer[0] и ES:[DI-1]->ABuffer[ADataSize-1]}
	mov bx,-1
	@InvertLoop:
	  dec di
	  mov al,[di]; movsb; mov [si][bx],al { обмен DS:[si] <-> ES:[DI] }
	  dec di
	loop @InvertLoop
      @SkipInvert:
    @End:
    mov ds,dx
  end;
end;
  {$Else IfNDef Delphi}
  register;
  {
       EAX = ANodeIndex  эрўры№э√щ єчхы
       EDX ->ABuffer   сєЇхЁ фы  фхъюфшЁютрээ√ї фрээ√ї
       ECX = ABufferSize  ЁрчьхЁ сєЇхЁр
       ёЄхъ -> ADataSize  ЁрчьхЁ фхъюфшЁютрээ√ї фрээ√ї
       ёЄхъ -> Dic  ёыютрЁ№
  }
var
  PBytes:tPBytesArray;
  PPredecessors:tPLineReferenciesArray;
begin
  {$IfOpt R+}
  if (ANodeIndex<=cCode_NewByte) then begin
    RunError(201);
  end;
  if (ANodeIndex>=Dic.Descriptors.FirstFree) then begin
    RunError(201);
  end;
 {$EndIf}
  PBytes:=Dic.Bytes;
  PPredecessors:=Dic.Predecessors;
  asm
  { фхъюфшЁєхь, эю!!! т сєЇхЁ ёшьтюы√ яюярфр■Є т юсЁрЄэюь яюЁ фъх  }
    push ebx; push esi; push edi
    mov edi,ABuffer { EDI->ABuffer[0]}
    mov ebx,ANodeIndex { EBX:=ANodeIndex }
    mov ecx,ABufferSize { ECX:=ABufferSize }

    { while BX>cRootIndex do }
    cmp ebx,cRootIndex; jbe @OkDecode
    mov edx,PPredecessors;
    jecxz @FailDecode { if ECX=0 then goto @FailDecode }
    mov eax,PBytes;
    add edi,ecx; dec edi { EDI->ABuffer[ABufferSize-1]}
    std
    @Loop:
      { ABuffer[EDI]:=PBytes^[EBX] }
      lea esi,[eax][ebx]; movsb
      { EBX:=PPredecessors^[EBX] }
      mov ebx,tIndex([edx][ebx*4])
      cmp ebx,cRootIndex
    loopnz @Loop { ECX:=ECX-1; if (ECX<>0) and (EBX<>cRootIndex) then goto @Loop }
    cld

    { яЁютхЁър яюыэющ фхъюфшЁютъш }
    jbe @OkDecode

    @FailDecode:
      { ═┼фхъюфшЁютрыш - эхфюёЄрЄюўэю ьхёЄр т сєЇхЁх }
      { ёўшЄрхь, ёъюы№ъю эх їтрЄрхЄ }
      mov eax,cRootIndex
      @LoopCount: { repeat }
	dec ecx
	{ EBX:=PPredecessors^[EBX] }
	mov ebx,tIndex([edx][ebx*4])
	cmp ebx,eax
      ja @LoopCount { until BX=cRootIndex }
      mov @Result,ecx { DecodeNode:= -эхїтрЄър ЁрчьхЁр сєЇхЁр }
    jmp @End

    @OkDecode: { фхъюфшЁютрэю тёх }
      inc edi; mov esi,edi
      sub edi,ABuffer; mov ecx,ABufferSize; sub ecx,edi
      mov @Result,ecx { DecodeNode:= ўшёыю срщЄ, яюьх∙хээ√ї т сєЇхЁ }
      mov edi,ABuffer
//      cmp esi,edi; je @End
      movzx eax,cl; and al,03H
      shr ecx,2
      rep movsd
      mov ecx,eax
      rep movsb
    @End:
    pop edi; pop esi; pop ebx
  end;
(*
  asm
  { фхъюфшЁєхь, эю!!! т сєЇхЁ ёшьтюы√ яюярфр■Є т юсЁрЄэюь яюЁ фъх  }
    push ebx; push esi; push edi
    mov edi,ABuffer { EDI->ABuffer[0]}
    mov ebx,ANodeIndex { EBX:=ANodeIndex }
    mov ecx,ABufferSize { ECX:=ABufferSize }

    { while BX>cRootIndex do }
    cmp ebx,cRootIndex; jbe @OkDecode
    mov edx,PPredecessors;
    jecxz @FailDecode { if ECX=0 then goto @FailDecode }
    mov eax,PBytes;
    @Loop:
      { ABuffer[EDI]:=PBytes^[EBX] }
      lea esi,[eax][ebx]; movsb
      { EBX:=PPredecessors^[EBX] }
      mov ebx,tIndex([edx][ebx*4])
      cmp ebx,cRootIndex
    loopnz @Loop { ECX:=ECX-1; if (ECX<>0) and (EBX<>cRootIndex) then goto @Loop }

    { яЁютхЁър яюыэющ фхъюфшЁютъш }
    jbe @OkDecode

    @FailDecode:
      { ═┼фхъюфшЁютрыш - эхфюёЄрЄюўэю ьхёЄр т сєЇхЁх }
      { ёўшЄрхь, ёъюы№ъю эх їтрЄрхЄ }
      mov eax,cRootIndex
      @LoopCount: { repeat }
	dec ecx
	{ EBX:=PPredecessors^[EBX] }
	mov ebx,tIndex([edx][ebx*4])
	cmp ebx,eax
      ja @LoopCount { until BX=cRootIndex }
      mov @Result,ecx { DecodeNode:= -эхїтрЄър ЁрчьхЁр сєЇхЁр }
    jmp @End

    @OkDecode: { фхъюфшЁютрэю тёх }
      mov ecx,edi; sub ecx,ABuffer { ECX:= ўшёыю фхъюфшЁютрээ√ї срщЄ }
      mov @Result,ecx { DecodeNode:= ўшёыю срщЄ, яюьх∙хээ√ї т сєЇхЁ }
      shr ecx,1 { ECX:=ECX div 2 }
      jecxz @SkipInvert { if ECX=0 then goto @SkipInvert }
	{ шэтхЁЄшЁєхь }
	mov esi,ABuffer { esi ->ABuffer[0] ш EDI-1 ->ABuffer[ADataSize-1]}
	mov ebx,-1
	@InvertLoop:
	  dec edi
	  mov al,[edi]; movsb; mov [esi][ebx],al {[esi]<=>[EDI]}
	  dec edi
	loop @InvertLoop
      @SkipInvert:
    @End:
    pop edi; pop esi; pop ebx
  end;
*)
end;
  {$EndIf}
{$EndIf}

{ возвращает ссылку на ближайший узел дерева в направлении ARight}
{ тючтЁр∙рхЄ ёё√ыъє эр сышцрщ°шщ єчхы фхЁхтр т эряЁртыхэшш ARight}
function NearestNodeRef(
	   var ANodeRef:tIndex; { исходная ссылка на корень дерева для поиска }
				{ шёїюфэр  ёё√ыър эр ъюЁхэ№ фхЁхтр фы  яюшёър }
	       ARight:boolean; { направление }{ эряЁртыхэшх }
	 const Nodes:tNodesArray
):tPIndex;
{ Указатель на ячейку, содержащую ссылку }
{ ╙ърчрЄхы№ эр  ўхщъє, ёюфхЁцр∙є■ ёё√ыъє }

{$IfNDef ASM}
  var pi,pi0:tPIndex;
begin
  {$IfOpt R+}
  if ANodeRef=cNilIndex then begin
    RunError(201);
  end;
  {$EndIf}
  pi:=@ANodeRef;
  if ARight then begin
    repeat
      pi0:=pi;
      pi:=@Nodes[pi^].Right;
    until pi^=cNilIndex;
  end else begin
    repeat
      pi0:=pi;
      pi:=@Nodes[pi^].Left;
    until pi^=cNilIndex;
  end;
  NearestNodeRef:=pi0;
end;
{$Else}
  {$IfNDef Delphi}
  assembler;
  asm
    les si,Nodes
    mov di,word(ANodeRef)
    mov bl,ARight; xor bh,bh; shl bx,1; add si,bx
    mov bx,es:[di]
    @Loop:
      mov ax,di
      shl bx,2
      lea di,[si][bx]
{      mov di,si; add di,bx}
      mov bx,es:[di]; or bx,bx;
    jnz @Loop
    mov dx,es
  end;
  {$Else IfNDef Delphi}
register;
  { EAX->ANodeRef;    DL= ARight;    ECX->Nodes; }
  asm
    push ebx
    movzx edx,ARight; shl dl,2;
    add Nodes,edx
    mov ebx,[ANodeRef];
    jmp @Enter
    @Loop:
      mov ANodeRef,edx
      @Enter:
      lea edx,[Nodes][ebx*8]
      mov ebx,[edx]; or ebx,ebx;
    jnz @Loop
    pop ebx
  end;
  {$EndIf}
{$EndIf}


{ возвращает:
  1) ссылку на ближайший узел дерева в направлении ARight;
  2) ссылку (ARefNodeIndex) на узел который ссылается на
     ближайший узел дерева в направлении ARight }
function xNearestNodeRef(
		 ANodeIndex:tIndex;
		 ARight:boolean;
	   const Nodes:tNodesArray;
	     var ARefNodeIndex:tIndex
):tPIndex;

{$IfNDef ASM}
  var p,p0:tPIndex; n0,n:tIndex;
begin
 {$IfNDef Delphi}
  p:=@Nodes[ANodeIndex].LeftRight[not ARight];
 {$Else}
  p0:=@Nodes[ANodeIndex].LeftRight[not ARight];
  p:=p0;
 {$EndIf}

  {$IfOpt R+}
  if p^=cNilIndex then begin
    RunError(201);
  end;
  {$EndIf}
  n:=ANodeIndex;
  if ARight then begin
    repeat
      p0:=p; n0:=n; n:=p^;
      p:=@Nodes[n].Right;
    until p^=cNilIndex;
  end else begin
    repeat
      p0:=p; n0:=n; n:=p^;
      p:=@Nodes[n].Left;
    until p^=cNilIndex;
  end;
  ARefNodeIndex:=n0;
  xNearestNodeRef:=p0;
end;
{$Else}
  {$IfNDef Delphi}
  assembler;
  asm
    { ES:si->Nodes}
    les si,Nodes
    { BX:= ANodeIndex}
    mov bx,ANodeIndex
    { ES:DI-> Nodes[ANodeIndex].LeftRight }
    mov dx,bx; shl bx,2; mov di,si; add di,bx;
    { BX:=2*Ord(ARight) }
    mov bl,ARight; xor bh,bh; shl bl,1
    { ES:SI-> Nodes.LeftRight[ARight] }
    add si,bx
    { ES:DI-> Nodes.LeftRight[not ARight] }
    xor bl,2; add di,bx

    { BX:=Nodes[ANodeIndex].LeftRight[not ARight] }
    mov bx,es:[di]
    @Loop:
      {AX это pi0: pi0:=pi}
      mov ax,di
      {СX это n0: CX:=n/DX/; n/DX/:=pi^}
      mov cx,dx; mov dx,bx
      { BX:= pi^}
      shl bx,2; {mov di,si; add di,bx;} lea di,[si+bx]; mov bx,es:[di];
      { until bx=cNilIndex; }
      or bx,bx
    jnz @Loop
    {DX:AX := pi0}
    mov dx,es
    { ARefNodeIndex := n0/CX/ }
    les di,ARefNodeIndex; mov es:[di],cx
  end;
  {$Else IfNDef Delphi}
  register;
  { EAX = ANodeIndex;  DL = ARight;   ECX -> Nodes;    ёЄхъ: ARefNodeIndex;  }
  asm
  push ebx; push esi; push edi
    { EDI-> Nodes[ANodeIndex].LeftRight }
    lea edi,[Nodes][ANodeIndex*8]
    { ARight:=4*Ord(ARight) }
    movzx edx,ARight; shl edx,2
    { ECX -> Nodes.LeftRight[ARight] }
    add Nodes,edx
    { EDI-> Nodes.LeftRight[not ARight] }
    xor edx,4; add edi,edx

    mov edx,ANodeIndex
    mov ebx,[edi]
    @Loop:
      mov eax,edi { Result:=EDI }
      mov esi,edx; mov edx,ebx
      lea edi,[Nodes][ebx*8]
      mov ebx,[edi]; or ebx,ebx
    jnz @Loop
    mov ebx,ARefNodeIndex; mov [ebx],esi
  pop edi; pop esi; pop ebx
  end;
  {$EndIf}
{$EndIf}

{ Переключает направление балансировки для ветви ARight дерева ANodeIndex }
{ ╧хЁхъы■ўрхЄ эряЁртыхэшх срырэёшЁютъш фы  тхЄтш ARight фхЁхтр ANodeIndex }
procedure SetNodesBalanceDirection(
	    ANodeIndex:tNodeIndex;
	    ARight:boolean;
	var Dic:tDictionary
);
{$IfNDef ASM}
begin
  if ARight then
    while ANodeIndex<>cNilIndex do begin
      Include(Dic.Flags^[ANodeIndex],nfRight);
      ANodeIndex:=Dic.Nodes^[ANodeIndex].Right;
    end
  else
    while ANodeIndex<>cNilIndex do begin
      Exclude(Dic.Flags^[ANodeIndex],nfRight);
      ANodeIndex:=Dic.Nodes^[ANodeIndex].Left;
    end
end;
{$Else IfNDef ASM}
  {$IfNDef Delphi}
assembler;
  const bitnfRight=(1 shl Ord(nfRight));
  asm
    mov dx,ds
    lds si,Dic
    les di,tDictionary([si]).Flags {ES:DI-> массив Flags}
    lds si,tDictionary([si]).Nodes {DS:SI-> массив Nodes}
    mov bx,ANodeIndex {BX:=ANodeIndex}
    cmp ARight,True; je @LoopR { if ARight=TRUE then GOTO @LoopR}

    @LoopL: { переключение балансировки влево }
      { while BX<>cNilIndex do }
      cmp bx,cNilIndex; je @EndLoop
      { Exclude(Dic.Flags^[BX],nfRight); }
      and es:tNodeFlags([di][bx]),not bitnfRight
      { BX:=Dic.Nodes^[BX].Left }
      shl bx,2; mov bx,tNode([si][bx]).Left
    jmp @LoopL

    @LoopR: { переключение балансировки вправо }
      { while BX<>cNilIndex do }
      cmp bx,cNilIndex; je @EndLoop
      { Include(Dic.Flags^[BX],nfRight); }
      or es:tNodeFlags([di][bx]),bitnfRight
      { BX:=Dic.Nodes^[BX].Right }
      shl bx,2; mov bx,tNode([si][bx]).Right
    jmp @LoopR

    @EndLoop:
    mov ds,dx
  end;
  {$Else}
  register;
  const bitnfRight=(1 shl Ord(nfRight));
{ EAX = ANodeIndex:tNodeIndex;
  DL =  ARight:boolean;
  ECX -> Dic:tDictionary}
  asm
    cmp ARight,True; je @LoopR0
    mov edx,tDictionary.Flags([Dic])
    mov ecx,tDictionary.Nodes([Dic])

    @LoopL:
      cmp eax,cNilIndex; je @EndLoop
      and tNodeFlags([edx][eax]),not bitnfRight
      mov eax,tNode([ecx][eax*8]).Left
    jmp @LoopL

    @LoopR0:
    mov edx,tDictionary.Flags([Dic])
    mov ecx,tDictionary.Nodes([Dic])

    @LoopR:
      cmp eax,cNilIndex; je @EndLoop
      or tNodeFlags([edx][eax]),bitnfRight
      mov eax,tNode([ecx][eax*8]).Right
    jmp @LoopR

    @EndLoop:
  end;
  {$EndIf}
{$EndIf NDef ASM}

{ переключение направления балансировки для узла }
{ яхЁхъы■ўхэшх эряЁртыхэш  срырэёшЁютъш фы  єчыр }
const
  bnfRight=(1 shl Ord(nfRight));

procedure SwitchBalanceDirection(
	   var AFlags:tNodeFlags
);
{ ВОЗВРАЩАЕТ: состояние балансировки до переключения }
{ ┬╬╟┬╨└┘└┼╥: ёюёЄю эшх срырэёшЁютъш фю яхЁхъы■ўхэш  }
{$IfNDef ASM}
begin
  if nfRight in AFlags then
    Exclude(AFlags,nfRight)
  else
    Include(AFlags,nfRight);
end;
{$Else}
  {$IfNDef Delphi}
assembler;
asm
  les si,AFlags
  xor es:tNodeFlags([si]),bnfRight
end;
  {$Else}
register;
asm
  xor tNodeFlags([eax]),bnfRight
end;
  {$EndIF}
{$EndIF}

{ Добавление узла ANodeIndex в дерево c корневым узлом ARootRef,
сохраняет идеальную балансировку. }
{ ─юсртыхэшх єчыр ANodeIndex т фхЁхтю c ъюЁэхт√ь єчыюь ARootRef,
ёюїЁрэ хЄ шфхры№эє■ срырэёшЁютъє. }
procedure AddNode(
	    ANodeIndex:tIndex; { индекс узла для вставки в дерево }
			       { шэфхъё єчыр фы  тёЄртъш т фхЁхтю }
	    ARootRef:tPIndex; { ссылка на корневой узел дерева }
			      { ёё√ыър эр ъюЁэхтющ єчхы фхЁхтр }
	var Dic:tDictionary { словарь (данные) } { ёыютрЁ№ (фрээ√х) }
);
  var Vbal,StopRepeat:boolean;
      b:byte;
      PBytes:tPBytesArray;
      PNodes:tPNodesArray;
      PFlags:tPFlagsArray;
      MidNodeRef1,MidNodeRef2:tPIndex;
      RootIndex,MidNode1Index,MidNode2Index:tIndex;
      MidNode2RefIndex:tIndex;
      OldFlags:tNodeFlags;
begin
  RootIndex:=ARootRef^;
  if RootIndex=cNilIndex then begin
   { Пустое дерево - вставка корневого узла дерева }
   { ╧єёЄюх фхЁхтю - тёЄртър ъюЁэхтюую єчыр фхЁхтр }
    ARootRef^:=ANodeIndex;
  end else begin { непустое дарево }
  { Добавление узла в дерево } { ─юсртыхэшх єчыр т фхЁхтю }
    { инициализация локальных указателей для ускорения обращения }
    { шэшЎшрышчрЎш  ыюъры№э√ї єърчрЄхыхщ фы  єёъюЁхэш  юсЁр∙хэш  }
    PBytes:=Dic.Bytes;
    PNodes:=Dic.Nodes;
    PFlags:=Dic.Flags;
    { проход по дереву до рассогласования балансировки и направления вставки }
    { яЁюїюф яю фхЁхтє фю Ёрёёюуырёютрэш  срырэёшЁютъш ш эряЁртыхэш  тёЄртъш }
    b:=PBytes^[ANodeIndex];
    StopRepeat:=false;
    repeat
      {$IfOpt R+}
	if (b=PBytes^[RootIndex]) then
	  RunError(201);
      {$EndIf}
      Vbal:=nfRight in PFlags^[RootIndex];
      if Vbal then
        Exclude(PFlags^[RootIndex], nfRight)
      else
        Include(PFlags^[RootIndex], nfRight);
      if Vbal = (b>PBytes^[RootIndex]) then begin
	ARootRef:=@PNodes^[RootIndex].LeftRight[Vbal];
	RootIndex:=ARootRef^;
      end else begin
	StopRepeat:=TRUE;
      end;
    until StopRepeat or (RootIndex=cNilIndex);
    if not StopRepeat then begin
    {  дошли до места - вставка узла на место }
    {  фю°ыш фю ьхёЄр - тёЄртър єчыр эр ьхёЄю }
      ARootRef^:=ANodeIndex;
    end else begin
    {   обнаружено рассогласование балансировки и направления вставки -
      необходимо переместить корневой узел в направлении балансировки }
    {   юсэрЁєцхэю Ёрёёюуырёютрэшх срырэёшЁютъш ш эряЁртыхэш  тёЄртъш -
      эхюсїюфшью яхЁхьхёЄшЄ№ ъюЁэхтющ єчхы т эряЁртыхэшш срырэёшЁютъш }
      {$IfOpt R+}
	if (PNodes^[RootIndex].LeftRight[Vbal]<>cNilIndex)
	  and (PNodes^[RootIndex].LeftRight[not Vbal]=cNilIndex) then
	  RunError(201);
      {$EndIf}
      { проверяем для корневого узла ссылку против направления балансировки }
      { яЁютхЁ хь фы  ъюЁэхтюую єчыр ёё√ыъє яЁюЄшт эряЁртыхэш  срырэёшЁютъш }
      if PNodes^[RootIndex].LeftRight[not Vbal]=cNilIndex then begin
       { ВЫРОЖДЕННОЕ дерево - состоит только из 1 узла }
       { ┬█╨╬╞─┼══╬┼ фхЁхтю - ёюёЄюшЄ Єюы№ъю шч 1 єчыр }
       { заменяем ссылку на корневой узел на ссылку на новый узел }
       { чрьхэ хь ёё√ыъє эр ъюЁэхтющ єчхы эр ёё√ыъє эр эют√щ єчхы }
	ARootRef^:=ANodeIndex;
       { перемещаем корневой узел в направлении балансировки }
       { яхЁхьх∙рхь ъюЁэхтющ єчхы т эряЁртыхэшш срырэёшЁютъш }
	PNodes^[ANodeIndex].LeftRight[Vbal]:=RootIndex;
       { сохраняем сведения по балансировке для нового корневого узела }
       { ёюїЁрэ хь ётхфхэш  яю срырэёшЁютъх фы  эютюую ъюЁэхтюую єчхыр }
	PFlags^[ANodeIndex]:=PFlags^[RootIndex];
      end else
      { проверяем для корневого узла ссылку в направлении балансировки }
      { яЁютхЁ хь фы  ъюЁэхтюую єчыр ёё√ыъє т эряЁртыхэшш срырэёшЁютъш }
      if PNodes^[RootIndex].LeftRight[Vbal]=cNilIndex then begin
       { ПОЛУВЫРОЖДЕННОЕ дерево - в направлении балансировки нет узла }
       { ╧╬╦╙┬█╨╬╞─┼══╬┼ фхЁхтю - т эряЁртыхэшш срырэёшЁютъш эхЄ єчыр }
	 { ищем ссылку на ближайший к корневому узел со стороны
	 против направления балансировки (not Vbal)}
	 { ш∙хь ёё√ыъє эр сышцрщ°шщ ъ ъюЁэхтюьє єчхы ёю ёЄюЁюэ√
	 яЁюЄшт эряЁртыхэш  срырэёшЁютъш (not Vbal)}
	 {!! ТАМ МОЖЕТ БЫТЬ БОЛЕЕ ОДНОГО УЗЛА, например,
	  разбалансированное дерево при рекурсии после удаления узла MidNode2 }
	 {!! ╥└╠ ╠╬╞┼╥ ┴█╥▄ ┴╬╦┼┼ ╬─═╬├╬ ╙╟╦└, эряЁшьхЁ,
	  ЁрчсрырэёшЁютрээюх фхЁхтю яЁш ЁхъєЁёшш яюёых єфрыхэш  єчыр MidNode2 }
	  MidNodeRef2:=xNearestNodeRef(RootIndex, Vbal, PNodes^, MidNode2RefIndex);
	 { запоминаем номер ближайшего к корневому узла со стороны
	  против направления балансировки}
	 { чряюьшэрхь эюьхЁ сышцрщ°хую ъ ъюЁэхтюьє єчыр ёю ёЄюЁюэ√
	  яЁюЄшт эряЁртыхэш  срырэёшЁютъш}
	  MidNode2Index:=MidNodeRef2^;
	 { сравниваем ближайший к корневому узел против направления
	  балансировки с новым узлом на предмет вставки в сторону
	  балансировки или против }
	 { ёЁртэштрхь сышцрщ°шщ ъ ъюЁэхтюьє єчхы яЁюЄшт эряЁртыхэш 
	  срырэёшЁютъш ё эют√ь єчыюь эр яЁхфьхЄ тёЄртъш т ёЄюЁюэє
	  срырэёшЁютъш шыш яЁюЄшт }
	  if (PBytes^[MidNode2Index]>b) <> Vbal then begin
	   { новый узел НЕ попадает в интервал субдерева в направлении против
	    балансировки - вставляем его вместо корня }
	   { эют√щ єчхы ═┼ яюярфрхЄ т шэЄхЁтры ёєсфхЁхтр т эряЁртыхэшш яЁюЄшт
	    срырэёшЁютъш - тёЄрты хь хую тьхёЄю ъюЁэ  }
	    PNodes^[ANodeIndex]:=PNodes^[RootIndex];
	    PFlags^[ANodeIndex]:=PFlags^[RootIndex];
	   {$IfOpt R+}
	    if (nfRight in PFlags^[ANodeIndex])=Vbal then
	      RunError(201);
	   {$EndIf}
	    { старый корневой узел сдвигаем в направлении балансировки }
	    { ёЄрЁ√щ ъюЁэхтющ єчхы ёфтшурхь т эряЁртыхэшш срырэёшЁютъш }
	    PNodes^[ANodeIndex].LeftRight[Vbal]:=RootIndex;
	    { удаляем ссылки старого корневого узла - он теперь внизу }
	    { єфры хь ёё√ыъш ёЄрЁюую ъюЁэхтюую єчыр - юэ ЄхяхЁ№ тэшчє }
	    PNodes^[RootIndex]:=cNullNode;
{??}	    PFlags^[RootIndex]:=[];
	    { вставляем ссылку на новый узел как на корень }
	    { тёЄрты хь ёё√ыъє эр эют√щ єчхы ъръ эр ъюЁхэ№ }
	    ARootRef^:=ANodeIndex;
	  end else begin
	   { новый узел попадает в интервал субдерева в направлении против
	    балансировки - перемещаем узел MidNode2 в корень }
	   { эют√щ єчхы яюярфрхЄ т шэЄхЁтры ёєсфхЁхтр т эряЁртыхэшш яЁюЄшт
	    срырэёшЁютъш - яхЁхьх∙рхь єчхы MidNode2 т ъюЁхэ№ }
	    ARootRef^:=MidNode2Index;
	    { заменяем ссылку на MidNode2 на субдерево узла MidNode2
	    против направления балансировки }
	    { чрьхэ хь ёё√ыъє эр MidNode2 эр ёєсфхЁхтю єчыр MidNode2
	    яЁюЄшт эряЁртыхэш  срырэёшЁютъш }
	    MidNodeRef2^:=PNodes^[MidNode2Index].LeftRight[not Vbal];
	    { корректируем возможную ошибку из-за перемещения субдерева
	     узла MidNode2 - неверное направление балансировки }
	    { ъюЁЁхъЄшЁєхь тючьюцэє■ ю°шсъє шч-чр яхЁхьх∙хэш  ёєсфхЁхтр
	     єчыр MidNode2 - эхтхЁэюх эряЁртыхэшх срырэёшЁютъш }
	    if (PNodes^[MidNode2RefIndex].LeftRight[not (nfRight in PFlags^[MidNode2RefIndex])]=cNilIndex) then
	      SwitchBalanceDirection(PFlags^[MidNode2RefIndex]);
	    { переносим в MidNode2 ссылки бывшего корневого узла }
	    { яхЁхэюёшь т MidNode2 ёё√ыъш с√т°хую ъюЁэхтюую єчыр }
	    PNodes^[MidNode2Index]:=PNodes^[RootIndex];
	    PFlags^[MidNode2Index]:=PFlags^[RootIndex];
	    { переключаем направление балансировки, поскольку субдерево
	    разбалансировано удалением MidNode2 в корень }
	    { яхЁхъы■ўрхь эряЁртыхэшх срырэёшЁютъш, яюёъюы№ъє ёєсфхЁхтю
	    ЁрчсрырэёшЁютрэю єфрыхэшхь MidNode2 т ъюЁхэ№ }
	    SwitchBalanceDirection(PFlags^[MidNode2Index]);
	    { удаляем ссылки бывшего корневого узла }
	    { єфры хь ёё√ыъш с√т°хую ъюЁэхтюую єчыр }
	    PNodes^[RootIndex]:=cNullNode;
{??}	    PFlags^[RootIndex]:=[];
	    { бывший корневой узел вставляем по направлению балансировки }
	    { с√т°шщ ъюЁэхтющ єчхы тёЄрты хь яю эряЁртыхэш■ срырэёшЁютъш }
	    PNodes^[MidNode2Index].LeftRight[Vbal]:=RootIndex;
	    { вставляем узел ANodeIndex
	      в субдерево против направления балансировки }
	    { тёЄрты хь єчхы ANodeIndex
	      т ёєсфхЁхтю яЁюЄшт эряЁртыхэш  срырэёшЁютъш }
	    SetNodesBalanceDirection(PNodes^[MidNode2Index].LeftRight[not Vbal], Vbal, Dic);
	    AddNode(ANodeIndex, @PNodes^[MidNode2Index].LeftRight[not Vbal], Dic);
	  end;
      end else begin
	{ ищем ссылку на ближайший к корневому узел со стороны
	 направления балансировки Vbal}
	{ ш∙хь ёё√ыъє эр сышцрщ°шщ ъ ъюЁэхтюьє єчхы ёю ёЄюЁюэ√
	 эряЁртыхэш  срырэёшЁютъш Vbal}
	MidNodeRef1:=NearestNodeRef(PNodes^[RootIndex].LeftRight[Vbal], (not Vbal), PNodes^);
	{ запоминаем этот узел } { чряюьшэрхь ¤ЄюЄ єчхы }
	MidNode1Index:=MidNodeRef1^;
	{ изымаем этот узел из дерева и заменяем корневым узлом дерева }
	{ шч√ьрхь ¤ЄюЄ єчхы шч фхЁхтр ш чрьхэ хь ъюЁэхт√ь єчыюь фхЁхтр }
	MidNodeRef1^:=RootIndex;

	{ ближайший к корневому узел со стороны (not Vbal)}
	{ сышцрщ°шщ ъ ъюЁэхтюьє єчхы ёю ёЄюЁюэ√ (not Vbal)}
	MidNodeRef2:=xNearestNodeRef(RootIndex, Vbal, PNodes^, MidNode2RefIndex);
	{ запоминаем номер ближайшего к корневому узла со стороны
	 против направления балансировки}
	{ чряюьшэрхь эюьхЁ сышцрщ°хую ъ ъюЁэхтюьє єчыр ёю ёЄюЁюэ√
	 яЁюЄшт эряЁртыхэш  срырэёшЁютъш}
	MidNode2Index:=MidNodeRef2^;
	{ сравниваем со вставляемым узлом }
	{ ёЁртэштрхь ёю тёЄрты хь√ь єчыюь }
	if (PBytes^[MidNode2Index]>=b) <> Vbal then begin
	{ просто вставляем новый узел, как корень }
	{ яЁюёЄю тёЄрты хь эют√щ єчхы, ъръ ъюЁхэ№ }
	  { переносим ссылки бывш. корня }
	  { яхЁхэюёшь ёё√ыъш с√т°. ъюЁэ  }
	  PNodes^[ANodeIndex]:=PNodes^[RootIndex];
	  PFlags^[ANodeIndex]:=PFlags^[RootIndex];
	  { переносим в бывш. корневой узел ссылки узла MidNode1 }
	  { яхЁхэюёшь т с√т°. ъюЁэхтющ єчхы ёё√ыъш єчыр MidNode1 }
	  PNodes^[RootIndex]:=PNodes^[MidNode1Index];
	  PFlags^[RootIndex]:=PFlags^[MidNode1Index];
	  { удаляем ссылки для узла MidNode1 }
	  { єфры хь ёё√ыъш фы  єчыр MidNode1 }
	  PNodes^[MidNode1Index]:=cNullNode;
	  PFlags^[MidNode1Index]:=[];
	  { вставляем новый узел, как корень }
	  { тёЄрты хь эют√щ єчхы, ъръ ъюЁхэ№ }
	  ARootRef^:=ANodeIndex;
	  { вставляем изъятый ранее узел MidNode1 в субдерево
	   в направлении балансировки }
	  { тёЄрты хь шч· Є√щ Ёрэхх єчхы MidNode1 т ёєсфхЁхтю
	   т эряЁртыхэшш срырэёшЁютъш }
	  {$IfOpt R+}
	   if MidNode1Index=cNilIndex then
	     RunError(201);
	  {$EndIf}
	  AddNode(MidNode1Index, @PNodes^[ANodeIndex].LeftRight[Vbal], Dic);
	end else begin
	{ перемещаем узел MidNode2 в корень }
	{ яхЁхьх∙рхь єчхы MidNode2 т ъюЁхэ№ }
	  { вставляем узел MidNode2 как корень }
	  { тёЄрты хь єчхы MidNode2 ъръ ъюЁхэ№ }
	  ARootRef^:=MidNode2Index;
	  { переносим в ссылку на MidNode2 субдерево MidNode2 }
	  { яхЁхэюёшь т ёё√ыъє эр MidNode2 ёєсфхЁхтю MidNode2 }
	  MidNodeRef2^:=PNodes^[MidNode2Index].LeftRight[not Vbal];
	  { переносим ссылки бывш. корня }
	  { яхЁхэюёшь ёё√ыъш с√т°. ъюЁэ  }
	  PNodes^[MidNode2Index]:=PNodes^[RootIndex];
	  PFlags^[MidNode2Index]:=PFlags^[RootIndex];
	  { переносим в бывш. корневой узел ссылки узла MidNode1 }
	  { яхЁхэюёшь т с√т°. ъюЁэхтющ єчхы ёё√ыъш єчыр MidNode1 }
	  PNodes^[RootIndex]:=PNodes^[MidNode1Index];
	  PFlags^[RootIndex]:=PFlags^[MidNode1Index];
	  { удаляем ссылки для узла MidNode1 }
	  { єфры хь ёё√ыъш фы  єчыр MidNode1 }
	  PNodes^[MidNode1Index]:=cNullNode;
{??}	  PFlags^[MidNode1Index]:=[];
	  { корректируем возможную ошибку из-за перемещения субдерева -
	   неверное направление балансировки }
	  { ъюЁЁхъЄшЁєхь тючьюцэє■ ю°шсъє шч-чр яхЁхьх∙хэш  ёєсфхЁхтр -
	   эхтхЁэюх эряЁртыхэшх срырэёшЁютъш }
	  if (PNodes^[MidNode2RefIndex].LeftRight[not (nfRight in PFlags^[MidNode2RefIndex])]=cNilIndex) then
	    SwitchBalanceDirection(PFlags^[MidNode2RefIndex]);
	  { вставляем узел ANodeIndex
	    в субдерево против направления балансировки }
	  { тёЄрты хь єчхы ANodeIndex
	    т ёєсфхЁхтю яЁюЄшт эряЁртыхэш  срырэёшЁютъш }
	  ARootRef:=@PNodes^[MidNode2Index].LeftRight[not Vbal];
	  OldFlags:=PFlags^[ARootRef^];
	  { переключаем направление балансировки, поскольку субдерево
	  разбалансировано удалением MidNode2 в корень }
	  { яхЁхъы■ўрхь эряЁртыхэшх срырэёшЁютъш, яюёъюы№ъє ёєсфхЁхтю
	  ЁрчсрырэёшЁютрэю єфрыхэшхь MidNode2 т ъюЁхэ№ }
	  SetNodesBalanceDirection(ARootRef^, Vbal, Dic);
	  AddNode(ANodeIndex, ARootRef, Dic);
	  { восстанавливаем указатель балансировки }
	  { тюёёЄрэртыштрхь єърчрЄхы№ срырэёшЁютъш }
	  ANodeIndex:=ARootRef^;
	  { корректируем возможную ошибку из-за перемещения субдерева -
	   неверное направление балансировки }
	  { ъюЁЁхъЄшЁєхь тючьюцэє■ ю°шсъє шч-чр яхЁхьх∙хэш  ёєсфхЁхтр -
	   эхтхЁэюх эряЁртыхэшх срырэёшЁютъш }
	  if (PNodes^[ANodeIndex].LeftRight[not (nfRight in OldFlags)]=cNilIndex) then
	    SwitchBalanceDirection(OldFlags);
	  PFlags^[ANodeIndex]:=OldFlags;
	  { вставляем изъятый ранее узел MidNode1 в субдерево
	   в направлении балансировки }
	  { тёЄрты хь шч· Є√щ Ёрэхх єчхы MidNode1 т ёєсфхЁхтю
	   т эряЁртыхэшш срырэёшЁютъш }
	  {$IfOpt R+}
	   if MidNode1Index=cNilIndex then
	     RunError(201);
	  {$EndIf}
	  AddNode(MidNode1Index, @PNodes^[MidNode2Index].LeftRight[Vbal], Dic);
	end;
      end;
    end;
  end;
end;

{ 4. Проход фрагмента в словаре }
function FindFragmentInDictionary(
	   const ABuffer;           { байты для поиска }{ срщЄ√ фы  яюшёър }
		 ABufferSize:tBufferIndex; { размер буфера }{ ЁрчьхЁ сєЇхЁр }
	   var   ARootIndex:tIndex; { ВХОД: номер корня для дерева,
					    откуда начинать поиск
					    (текущий фрагмент);
				     ВЫХОД: последний найденный узел
					    (не изменяется, если ничего
					    не найдено)}
                                    { ┬╒╬─: эюьхЁ ъюЁэ  фы  фхЁхтр,
					    юЄъєфр эрўшэрЄ№ яюшёъ
					    (Єхъє∙шщ ЇЁруьхэЄ);
				     ┬█╒╬─: яюёыхфэшщ эрщфхээ√щ єчхы
					    (эх шчьхэ хЄё , хёыш эшўхую
					    эх эрщфхэю)}
	   const Dic:tDictionary    { словарь }{ ёыютрЁ№ }
):tBufferIndex;
{ ВОЗВРАЩАЕТ: 1) размер фрагмента, найденного в буфере и
  2) номер последнего узла фрагмента в ARootIndex }
{ ┬╬╟┬╨└┘└┼╥: 1) ЁрчьхЁ ЇЁруьхэЄр, эрщфхээюую т сєЇхЁх ш
  2) эюьхЁ яюёыхфэхую єчыр ЇЁруьхэЄр т ARootIndex }

{$IfNDef ASM}
  var PNodes:tPNodesArray; b0,b:tByte;
      PBytes:tPBytesArray; i,j,j0:tIndex;
      PSuccs:tPLineReferenciesArray;
begin
  { инициализация вспомогательных переменных }
  { шэшЎшрышчрЎш  тёяюьюурЄхы№э√ї яхЁхьхээ√ї }
  PNodes:=Dic.Nodes;
  PBytes:=Dic.Bytes;
  PSuccs:=Dic.Successors;

  { поиск фрагмента }
  { яюшёъ ЇЁруьхэЄр }
  i:=0; j0:=ARootIndex;
  while (i<ABufferSize) do begin
    { j := корневой узел дерева-продолжения }
    { j := ъюЁэхтющ єчхы фхЁхтр-яЁюфюыцхэш  }
    j:=PSuccs^[j0];
    { поиск следующего байта b0 }
    { яюшёъ ёыхфє■∙хую срщЄр b0 }
    b0:=tBuffer(ABuffer)[i];
    { установка барьера }
    { єёЄрэютър срЁ№хЁр }
    PBytes^[cNilIndex]:=b0;
    { поиск байта }
    { яюшёъ срщЄр }
    b:=PBytes^[j];
    while b<>b0 do begin
      j:=PNodes^[j].LeftRight[b0>b];
      b:=PBytes^[j];
    end;
    if j<>cNilIndex then begin
      Inc(i);
      j0:=j; { найденное продолжение }{ эрщфхээюх яЁюфюыцхэшх }
    end else begin
      ABufferSize:=0; { прерываем цикл while }{ яЁхЁ√трхь Ўшъы while }
    end;
  end;
  { возвращаем длину фрагмента }
  { тючтЁр∙рхь фышэє ЇЁруьхэЄр }
  FindFragmentInDictionary:=i;
  { возвращаем значение индекса для последнего найденного узла }
  { тючтЁр∙рхь чэрўхэшх шэфхъёр фы  яюёыхфэхую эрщфхээюую єчыр }
  ARootIndex:=j0;
end;
{$Else IfNDef ASM}
  {$IfNDef Delphi}
assembler;
  var PNodes:tPNodesArray;
      PSuccs:tPLineReferenciesArray;
asm
  push ds
  { инициализация вспомогательных переменных }
    { DS:SI -> Dic }
    lds si,Dic
    les di,tDictionary([si]).Nodes
    mov word(PNodes),di; mov word(PNodes)[2],es
    les di,tDictionary([si]).Successors
    mov word(PSuccs),di; mov word(PSuccs)[2],es

    { ES:DI -> Dic.Bytes^ - эти регистры далее не меняются }
    les di,tDictionary([si]).Bytes

    { AX= индекс буфера (i)}
    xor ax,ax;

    { CX=конец текущего фрагмента (j0)}
    lds si,ARootIndex; mov cx,[si]

    @Loop: cmp ax,ABufferSize; jae @EndLoop { проверка не вышел ли AX за размеры }

      { DL=текущий байт (tBuffer(ABuffer)[i]) }
      lds si,ABuffer; mov bx,ax; mov dl,[si][bx]

      { BX=индекс корневого узла продолжения (j)}
      lds si,PSuccs; mov bx,cx; shl bx,1; mov bx,[si][bx]

      { DS:SI -> Dic.Nodes^ }
      lds si,PNodes
      { установка барьера: PBytes^[cNilIndex]:=AByte;}
      mov es:[di],dl
      { поиск очередного байта }
      @LoopFind:
	{ сравниваем DL с байтом текущего узла }
	cmp es:[di][bx],dl; je @EndFind { байт найден - выходим }
	rcl bx,2; mov bx,tIndex(tNode([si][bx]).LeftRight)
      jmp @LoopFind
      @EndFind:
      { BX=номер найденного узла }
      or bx,bx; jz @EndLoop { BX=0 - выходим, продолжение не найдено }
	{ BX<>0 - продолжение найдено }
	inc ax { увеличить индекс буфера }
	mov cx,bx { запомнить найденное продолжение }
    jmp @Loop
    @EndLoop:
    { возвращаем конец найденного фрагмента }
    lds si,ARootIndex; mov [si], cx
    { и длину фрагмента в AX }
  pop ds
end;
  {$Else}
   register;
{  EAX->ABuffer;
   EDX=ABufferSize;
   ECX-> ARootIndex;
   Stack->Dic
}
  var PBufferEnd:tIndex; PBuffer:tIndex;
asm
  push ebx; push esi; push edi
    add ABufferSize,ABuffer
    mov PBufferEnd,ABufferSize
    mov PBuffer,ABuffer
    mov ebx,[ARootIndex]
    @Loop: cmp ABuffer,PBufferEnd; jae @EndLoop
      { ESI-> Dic}
      mov esi,Dic
      { EBX:=эюьхЁ єчыр-яЁюфюыцхэш }
      mov edi,tDictionary([esi]).Successors; mov ebx,[edi][ebx*4]
      { EDI-> Dic.Bytes^ }
      mov edi,tDictionary([esi]).Bytes
      { ESI-> Dic.Nodes^ }
      mov esi,tDictionary([esi]).Nodes
      { DL:=ёыхфє■∙шщ срщЄ }
      mov dl,[ABuffer];
      { єёЄрэютър срЁ№хЁр Dic.Bytes^[0]:=DL}
      mov [edi],dl
      @LoopFind:
	{ ёЁртэштрхь DL ё срщЄюь Єхъє∙хую єчыр }
	cmp [edi][ebx],dl; je @EndFind { срщЄ эрщфхэ - т√їюфшь }
	rcl ebx,3; mov ebx,tIndex(tNode([esi][ebx]).LeftRight)
      jmp @LoopFind
      @EndFind:
      { EBX:= эюьхЁ эрщфхээюую єчыр }
      or ebx,ebx; jz @EndLoop
	inc ABuffer
        { ARootIndex:=EBX }
	mov [ARootIndex],ebx
    jmp @Loop
    @EndLoop:
    { EAX:= ЁрчьхЁ сєЇхЁр }
    sub ABuffer,PBuffer
  pop edi; pop esi; pop ebx
end;
  {$EndIf}
{$EndIf NDef ASM}
END.