Упаковка сэмплов без потерь.

   (Original was sent to ZK-System/Excess.
Ответа не получено)

   Как известно, в ESE имеется такая опция
"Compress sample",которая вроде как не ра-
ботает.И зря не работает,потому что сэмплы
имеют обыкновение  занимать  слишком много
места  на  диске, и запаковать их вовсе не
мешает.
   Я тут написал упаковщик сэмплов без по-
терь по методу DAKX.
   Небольшая, но глючная дока,иллюстрирую-
щая этот метод,прилагается. Путём экспери-
ментов  я нашёл самую плотную  упаковку из
семейства DAKX. Короче,изменения такие:
   - Пакуется, сам  понимаешь, дельта  код
(который считается в рилтайме);
   - Начальный размер "байта" равен 4 бита
+ знак;
   - У кода-расширителя нет знака;
   - У 0 и -1 нет знака;
   - Ширина следующего кода предсказывает-
ся линейной  экстраполяцией от двух преды-
дущих значений (значений дельта кода, а не
ширины).

   Программы:
DAKX3s+ - упаковщик
DAKX6-t - самый медленный распаковщик (без
 таблицы)
DAKX6t - такой же,но с таблицей в 256 байт
 Соответственно,быстрее.
unDAdup6 - быстрый,но длинный распаковщик,
 тоже с таблицей.

   Могу написать ещё более быстрый упаков-
щик (по  тому же методу и с той же скорос-
тью, что и unDAdup6). Более того,можно на-
писать ещё более быструю упаковку/распако-
вку,но соотв.упаковщики/распаковщики будут
в 2,4 или 8 раз (в зависимости от желаемой
скорости) длиннее... Сам оптимизировать не
пытайся, только  прогу  заглючишь (а ты не
представляешь, как  трудно  искать глюки в
пакерах!). Все  кажущиеся тормознутости на
самом деле тормознутостями не являются :).
   Для прикола процесс упаковки/распаковки
идёт под аккомпанимент COVOX'а.Порт ковок-
са - в константе PRN.

   Все инкременты адресов происходят через
подпрограммы,так что легко добавить перек-
лючение страничек.

   Вот  я думаю  пропихнуть этот метод как
стандарт и написать цифровой муз. редактор
под это дело.
   Плотность  и  скорость  упаковки можешь
сам заценить. Во всяком случае,это быстрее
и плотнее,чем hrust ;). Поскольку скорость
большая, то лучше опцию "Compress" переде-
лать  во  флажок  и паковать/распаковывать
каждый раз  при отгрузке/погрузке. Кстати,
что  у тебя там  ESE отгружает в параметре
Start? Вот там самое милое дело предусмот-
реть битик под эту хрень.

   Короче, когда  выпустишь (выпустишь или
мне сорцы отдашь?) ESE с упаковкой,то ЧТО-
БЫ HELP  К ESE БЫЛ ОБЯЗАТЕЛЬНО, И ПРИ ЭТОМ
САМЫЙ ПОЛНЫЙ! Иначе я не согласен ;)

   Между прочим,4-битные сэмплы тоже паку-
ются,причём свирепо!

   В общем,ты понял,к чему я клоню...даёшь
Last Hero на один диск ;).

─ Echomail (2:5029/37.2) ───── RU.COMPRESS
 Msg  : 24 of 33
 From : Maxime Zakharov       2:5065/10.12    26 Apr 99  22:23:14
 To   : All                      27 Apr 99  04:48:45
 Subj : DAKX method
──────────────────────────────────────────
Hello All,

http://dakx.com

==========================================

Introduction

A message N binary digits long contains N
bits of information. In isolation, it can
specify one of 2N possible messages.

     (Since 1.443 is the natural logarithm
of two [2 = e1.443], N/1.443 is the
natural unit of information, called "nats"
or "Boltz" in honor of the brilliant man
who first used the concept to derive many
powerful and remarkably enduring results
in thermodynamics.)

Thus a one bit "code" can specify one of
two messages, a two bit code one of four,
a three bit code one of eight, and so on.
If the message is to represent a signed
integer, it is convenient to interpret it
as a binary number in two's complement
notation (since that's how most computers
do arithmetic):

      Three Bit Code
  Binary  Interpretation
   100          -4
   101          -3
   110          -2
   111          -1
   000           0
   001           1
   010           2
   011           3

       Two Bit Code
  Binary  Interpretation
    10          -2
    11          -1
    00           0
    01           1

       One Bit Code
  Binary  Interpretation
     1          -1
     0           0


Suppose we need to send the seven digits
0,1,-2,-1,3,1,0. This could be done with
the seven messages

  0 01 10 1 110 01 0

as long as the person receiving this
information can keep track of the boundary
between messages. If sent in writing we
could leave gaps as above, or if
transmitted serially we could pause a bit
between messages (as in Morse code or
phase-encoded chroma signals). But if the
messages are left in computer memory or on
disk, we can't just save the bits all
packed together. If we allow them to run
together the recipient will see
001101110010 and will not be able extract
our digits [The first three bits, 001,
might mean 0,0,-1 or 0,1 or just 1].

How can we identify the message boundaries
in computer memory? One method is to
expand each message to a fixed number of
bits; putting the above into 8-bit "bytes"
results in

00000000 00000001 11111110 11111111
 00000011 00000001 00000000

which will obviously take a lot of extra
memory. In very early computers, when
memory was expensive and the size of a
refrigerator, memory usage was kept to a
minimum by using "field marks" to identify
message boundaries. Since memory has
become compact and inexpensive the modern
trend is to use even more of it, expanding
to 32 or even 64 bits. But there are still
times when a more efficient use is
desirable - if power for memory is
limited, or when sending through a slow
channel, or trying to fit a large amount
of information on a single disk.


So one object of data compression is to
pack a "uniquely decipherable" series of
messages as tightly as possible.
One method is to use "instantaneous"
codes, chosen such that no code is the
prefix of any other. The classic Huffman
codes fall into this category. Another is
to use a code length which implicitly
follows the size of a dynamic lookup-table
dictionary, as in LZW. A third is to
switch between differently-sized
dictionaries (and code lengths) based on
the preceding message content
(block-coding, context-sensitive, Markov
methods).

In the DAKX method, message boundaries
("code lengths") are determined through a
set of rules based on a combination of the
previous code length and previous code
value. One such set of rules might be:

1) The first code length is three bits.
2) If the previous code required the full
   code length, the next code will be the
   same length.
3) If the previous code did not require
   the full code length, the next code
   will be one bit shorter.
4) If the previous code was the "expand"
   code (the most negative number for that
   field length) discard it; the next code
   will be one bit longer.

For example, using the above table, the
encoding of the digits 0,1,-2,-1,3,1,0
would become:

1) 000  Encode  0 in 3 bits, reduce width
       to 2, since  0 requires only 1 bit.
2)  01  Encode  1 in 2 bits,   keep width
       at 2, since  1 requires 2 bits
3)  10  Encode -2 in 2 bits,   keep width
       at 2, since -2 requires 2 bits.
4)  11  Encode -1 in 2 bits, reduce width
       to 1, since -1 requires only 1 bit.
5)   1  -1, the "expand" code for width 1,
       increase width to 2
6)  10  -2, the "expand" code for width 2,
       increase width to 3
7) 011  Encode  3 in 3 bits,  keep width
       at 3
8) 001  Encode  1 in 3 bits, reduce width
       to 2, since 1 requires only 2 bits.
9)  00  Encode  0 in 2 bits, reduce width
       to 1, since  0 requires only 1 bit.

It can be seen that this simple method
will dynamically adjust itself to the
required field widths, providing efficient
packing as long as they do not change very
often.

An inefficiency of the method is the
inclusion of the occasional extra sign
bit, as in lines 1,4,8,9 above. Another is
the three extra bits used for the expand
codes in lines 5,6. Even so, it requires
just 8 extra bits to delimit the
boundaries of the seven digits. The JPEG
baseline method for encoding DC
coefficients requires at a minimum 2 bits
per boundary.


Many extensions to the basic rules are
possible. A "fast field increase" rule can
avoid more than two expand codes in a row,
by exploiting the fact that any data code
following an expand code must require the
full field width. A repeat count mechanism
can be implicitly triggered after one or
more repeats. A delay can be introduced
after an expand code before implicit field
reductions begin again. Instead of the
fixed threshold of rule 3 above,
a variable threshold can be used to
trigger field reduction, as well as
expansion. Field widths can be changed by
more than one bit at a time. And
completely different rules can be adopted
for each field width.

However, the simple rules often work
remarkably well. One advantage of this
method over instantaneous variable-length
codes is that the decoder will know the
width of each code in advance, so that it
can often be extracted in a single machine
cycle. This avoids the need for bit-by-bit
shifting and comparison against code
tables, and makes possible high-speed
processer decoding as well as inexpensive,
low power hardware implementations.

 (R) 1999 DAKX, LLC. All rights reserved
──────────────────────────────────────────

P.S.: Лучше  будет  не предусматривать би-
тик, а оставить  параметр Start для адреса
зацикливания. У упакованных сэмплов  пусть
будет расширение <D> (DATA). У неупакован-
ных <I>.
   Упаковка сэмплов без потерь просто нео-
бходима  для написания музыкального редак-
тора  под  мегабайт (назовём  его, скажем,
Quartz Tracker ;), когда неупакованный мо-
дуль  с сэмплами просто не уместился бы на
диске.
   Есть возможность поднять плотность упа-
ковки  с помощью использования какого-либо
фильтра  перед сжатием. Фильтр должен уда-
лять  избыточность, связанную, например, с
тем,что звуковой сэмпл в чём-то достаточно
периодичен... Естественно,такой фильтр до-
лжен быть обратимым.
   Но скорость понизится.
   А она и так не космическая. Ведь допус-
тим,что у нас Turbo,и используем мы какую-
нибудь  быструю реализацию метода (памяти-
то у нас много ;). Имеем 20k/sec.Пусть мо-
дуль имеет 400k сэмплов. Значит,после заг-
рузки  их нам придётся ждать 20 секунд ;(.
Другой  вопрос, что  они и грузиться будут
почти столько же времени ;).
   Исходники упаковщиков/распаковщиков ищи
в приложении.
   Этот  метод  я использовал, когда писал
WOLF 3D под Sound Blaster.У меня тогда бы-
ло 128k,и не хватало памяти,чтобы отассем-
блировать программу с неупакованными сэмп-
лами :)