Scenergy #02 31 декабря 1999

Программирование

Coding - The principle of packing animations in the demo JAM.

         Packing animations JAM

 In this article we will consider a method
Packing animations, used in the last
Deme Digital Reality - JAM (2 nd place in the
CC'999).

 If you have already seen this demo (and I hope
seen), then you know about any
animation question.

 I must say that I certainly am not
packaging specialist data and
so I can not guarantee the accuracy of
his statements, as well as the correctness
I have eaten here the terminology.

 Recently, the use of animation
as part of the demos is becoming more
popular. However, as a rule, people
use the so-called chunk'ovye animation, ie,
Animation in the resolution of 64x32 or 64x48 in
16 gradations of brightness and the amount of "points" 4x4
pixel. Granted, it's not bad. But with
time begins to pall. In addition,
this type of animation is not quite
suited to our plans
relatively JAM'a - we needed
animation is in the planar mode, ie in
resolution of 256x192, and in 2 colors as all
still dancing figures were to be
silhouette. In addition, it was necessary
keep a few criteria:

 - The maximum degree of packing.
 - Max high speed

   unpacker / player. Indeed, it was

   must decompress frame animation

   at 50 or 25 fps.

 Go tell that what was done
when writing JAM fully responsible
the above requirements. Judge for yourself
Here statistics of real data from our
demos:
Number of animations: 14
The total number of frames: 686
The volume of uncompressed data: 1,585,314 bytes
The volume of compressed data: 162.517 bytes
Compression ratio: 10.25%

 In this animation can be further
shrink HRUST'om somewhere else of interest on
20-30, ie, 2.5 Standard TR-DOS
drive animations easily fit in
100 with a small kilobytes. In addition, I
say that if we had more
time, it would be possible to achieve even
better compression quality used two
Additional features:

 - Packaging of animation frames, taking into account

   that the frames form a sequence

   ie not really packing staff, and

   differences between them. In JAM'e also due to

   lack of time was used

   player, playing only a short animation

   as a set of independent specialists. However, in

   packer, this mode is supported, and

   I can say that winning at this

   obtained a small (only a few

   percent).

 - Additional processing staff for

   smoothing the contours of the image. Because

   the fact that the animation frames for JAM

   hand-cut, their edges turned

   rather rough that respectively

   reduces the quality of packaging.

 Before we proceed directly to
description of compression algorithms, I must
to thank Dmitry Pyankov,
author of such well-known programs as HRUST,
HRUM and Laser Compact. He gave me
invaluable assistance in developing the format
compressed data, and it was his
advice and recommendations I had
achieve this quality package.

 So, first determine that
what we want to get a result. Us
need to pack the image. Moreover,
because this algorithm was developed
Packaging strictly defined types
images and takes into account their specificity, the
to describe what is this
specificity. Thus, the image that will be
about packing well, it should be:

 - Planar, ie, its format is similar to
format standard Spectrum
screen, where 1 byte is an 8
consecutive pixels on the screen.

 - Silhouette. The image is
a solid silhouette of a figure (in
JAM is the case with the figure of a dancing
person). Ideally, this silhouette is not
includes internal openings and halftones.
Ie scanned images, conversion
performed using dithering'a,
images with a large number of small
details, and pixel garbage, and other
Images of this kind will huddle
bad.

 - Single, ie the frame is shown
only one figure or more is not
interconnected shapes. Under
lack of communication here refers
that in each byte image
are part of only one figure. K
related parts are also close
located part of nonconvex shapes
(Eg, foot man standing upright).
To better understand what is at stake
Look at the picture below.



  Figures are not related figures relate

 This is certainly not a prerequisite, but
compliance with it will improve the quality of the package.

 Now that we understand to what
images will be about packing the best
way of using this method,
necessary to define two more very
important components, which, in effect, and
determine the format of compressed data, and
hence, a compression algorithm. It's a way
decoding the image and the way
encoding compressed data.

 By recoding the image I'm here
mean in what sequence
will be processed bytes Source
image.
 For the type of images that we
are going to shrink, fit 3 methods
conversion:
 1) The image represents the usual
Spectrum screen. Plus, this method
that, when unzipped will not have to
deal with calculating the display address
Indoor decompressed bytes as in
memory bytes are decompressed images
will be arranged in series. However,
using this method can be
will only compress image size
with the whole screen, which makes this method
inapplicable.

 2) The image is a sprite
encoded on the lines of:


                   0123

                   4567

                   89AB

                   CDEF

 This will remove the restriction on
fixed size of the animation. In addition,
with this method, conversion screen
address while unpacking required only when
transition to the next line of the screen that
saves time unpacking.
 3) The image is a sprite
encoded by columns:


                   048C

                   159D

                   26AE

                   37BF

 This method has the highest consumption
time to recalculate the display address -
calculation is performed for each byte.
However, this method has one big
advantage over other methods.
It is caused by the specific Spectrum
screen. As you know - the screen Spectrum
consists of familiarity. Each familiarity
appears on the screen as a square 8x8
pixels. However, the memory that does not 64
bytes, and only 8 bytes because 1 point for
screen corresponds to a single bit, but not
bytes. I apologize for what I say to all
certain things, but it is important for understanding
essence. So, if you look at how
are the bytes constituting familiarity,
we see that they are
vertically. Ie if you arrange them in
memory sequentially, then the probability
that these bytes form a homogeneous
sequence (which, naturally,
well-packed) is much higher than when
using a sequence of bytes
forming a horizontal line. And this
sequence of bytes we just
obtain in the case of conversion source
images in the form of a sprite with the encoding
columns. I'll tell you that when
Using this method, the quality of
packing animations from JAM increases already in the 3
(Three) times! So for the sake of this
increase the quality of compression is to take
certain disadvantages associated with
the need to recount the screen addresses.

 As you can imagine - the best choice
Third method, although the packer is also just
case supports the 2 nd method.

 Now let's consider the second
component - a way of coding data
When packing.
 As you probably know - there is
a variety of techniques packing. However,
all methods give high quality
packing us in this case do not fit
as they use the storage of packaged
data as a bitstream, and operations
bits on the Spectrum - a thing quite
slow and does not conform to
speed unpacker.

 "We'll go the other way!" (C), Lenin

 To increase the processing speed will
store the compressed data as a set
bytes. Accordingly, packed in a frame
We will represent a set of blocks
data in the following format:

+0 [Byte] type of operation. In the same byte

          to save space, we will store

          additional flags.
+1 [Data] length of the sequence.
+ N [data] Additional data.

 Naturally, all data except the byte
type of operation can change the size or
absent.
 You must also select a set of operations
that will be used unpacker
to restore the packed frame.
 Based on the specifics of the image that
we're going to pack, have been selected
The following types of operations (given in brackets
the names of these operations are used in
below):
 - Skip groups of bytes (Skip).
 - Inversion of bytes (Inverse).
 - Filling group B specific

   value (Fill byte).
 - Filling group B value # FF

   (Fill # FF).
 - Filling group B value # 00.

   (Fill # 00).
 - Placing a special memory. bytes.

   (Spec. byte).
 - Putting in memory of the sequence

   B (Sequence).
 Some explanation of the selected
types of operations.

 Operation "pass" and "inversion" of the group
bytes apply only if the images
animation, packed with the preceding
frame. But the extractor used in the JAM
supports unpacking only independent
compressed frames so that these type 2
operations did not really need. However, given
that in future it will be possible to write and
unpacking of a sequence of frames -
had to introduce and implement these 2 types
operations.

 Filling in the group B values ​​# 00 and
# FF made in separate operations based on
the specifics of the image as pakuemogo
these values ​​will occur
most often.
 Operation room in memory of specials. Byte "
also introduced based on the specifics pakuemogo
image. The fact that the bytes
forming the boundary of the silhouette of the object
will also occur quite often.
But of all the possible values ​​of these
bytes for the image, the specifics of which
been agreed at the outset, only 16:

         % 01% 10

         % 011% 100

         % 0111% 1000

         % 01% 10

         % 0001% 1110

         % 001% 110

         % 01% 10

         % 1% 0
 Thus, the imposition of these bytes
separate operation will get rid of
Operation room sequence
bytes, which would apply to these
bytes and will result in a gain in
of the packed image.

 In addition to all of the above is still
a couple of points designed to reduce the size of
packaged image.

 When packing frames are often found
situation where there are two well-pakuyuschiesya
sequences separated by only one
byte. A typical example - the boundary of the object.
We have a sequence # FF, then
byte boundaries of the object and behind it there is a big
sequence # 00. Respectively
bytes on an object to be packaged as
sequence of 1 byte, which is very
uneconomical. Therefore, for each operation
introduce an additional flag to be stored
in the 0-th bit of byte type of operation - a sign
that after this operation
need to be placed in another frame
byte, whose value is recorded immediately
after the data for this operation. There is one
exception to this rule - for operation
premises of the sequence of bytes that
flag is absent because makes no sense.

 Also, to improve performance
unpacker animations introduce another
additional code - a sign of the end of the frame.
The introduction of this code eliminates
unpacking from the need to count
size is the uncompressed data and it
saves valuable time.

 Now, when all types of operations are described,
We now describe another important
things - the way of coding length pakuemoy
sequence.

 We need to be able to specify
large size of the sequence in
using as little as possible
volume of data. Dima Pyankov proposed
the following method:
 Under each operation is given a
a certain number of codes. Let us assume for
operation of filling a byte # FF play
50 codes starting with code 80. Subtracting from the code
transaction value of the initial operation code
(In this case - 80) we obtain the length
sequence. Bit 0 contains the sign
that after the operation must be
save the extra byte of data. So
that all we have 50 / 2 = 25 different codes
sequence length. We call this
length limit.

 So, we have long sequences.
First check - if this length does not
is 0, then it will be long;
actual length is stored in the next byte.
We take this byte and check - more than he
limit the length of this operation (in our case
25)? If there are - then this is the length.
If not - then it is only the most significant byte
actual length, and least significant byte is stored
the next byte of data.
 Thus, this method of coding
with a limit of length N allows you to create
sequences with length up to N * 256 255.
For example, for our case (the length limit
equal to 25) the size of the sequence may
be up to 25 * 256 +255 = 6655 bytes, ie
even more than the screen size!

 Length limit for each operation and its
depends on how many codes allocated
to encode the operation. Because each
operation has its own probability of occurrence
When packing the frame, then the number of codes
allocated to them differently. Here is a table
distribution of codes between operations. In
JAM'e was used slightly different
table, but my changes
as a result was given to improve the quality
Packing for a test animation to 3%


       Type of Entry Number

     operation code codes


    Skip 0 (# 00) 32 (# 20)

    Inverse 32 (# 20) 16 (# 10)

    Fill byte 48 (# 30) 32 (# 20)

    Fill # FF 80 (# 50) 50 (# 32)

    Fill # 00130 (# 82) 50 (# 32)

    Spec. byte 180 (# B4) 32 (# 20)

    Sequence 212 (# D4) 43 (# 2B)

    End marker 255 (# FF) 1 (# 01)


 Well, as usual, there are a couple of exceptions
Rules:
1) For operations Fill # FF and Fill # 00 Length
sequence of 1 byte is not required
as it can be encoded in room
frame appropriate professional. bytes. Therefore,
length limit for these operations increased by
1 due to the fact that really is not stored
limit and the limit-1.
2) To End marker length limit is not specified.

 I will say a few words about the file format for
Storage of animations. In fact, their 2 - Format
Storage individually packed frame
and direct the animation.

Format for storing a single frame (ZXF)

+0 [Data] 'ZXF' (ZX Frame). Signature on

          which can define the format

          file.
+3 [Byte] version of the file format. Availability

          the byte enables you to easily

          determine the file format that

          may vary over time. On

          the moment the current version

          format - # 01.
+4 [Byte] byte flags. The content of this

          bytes to determine the type

          packaging that was used

          for this file and use the

          the corresponding player.

          Learn more about the meaning of each

          flag, see below.
+5 [Byte] X coordinate of the upper-left

          corner of the window to display frames.
+6 [Byte] Y coordinate of the upper-left

          corner of the window to display frames.
+7 [Byte] Size of frame X.
+8 [Byte] Size of frame Y.
+9 [Data] Packed data.

 It should be noted that since This algorithm
package works with the sequence
bytes, the X coordinate and the size of X will
always multiples of familiarity. Respectively
These parameters are set in familiarity. Ie
value of X coordinate value of 5 means
that the upper left corner of the window frame O
is from 5 familiarity, rather than
5 pixel screen. Same thing with the size of
on X. The relevant parameters for Y
are given in pixels.



    Format for storing animations (ZXA)

+0 [Data] 'ZXA' (ZX Animation). Signature

          on which we can determine

          file format.
+3 [Byte] version of the file format. Availability

          the byte enables you to easily

          determine the file format that

          may vary over time. On

          the moment the current version

          format - # 01.
+4 [Byte] Number of frames in the animation.
+5 [Byte] byte flags. The content of this

          bytes to determine the type

          packaging that was used

          for this file and use the

          the corresponding player.

          Learn more about the meaning of each

          flag, see below.
+6 [Data] Table displacement data start

          each frame of animation. For a point

          reference displacement takes the first

          bytes of compressed data. So

          displacement of the first frame is always

          will be zero. Table size:

          2 * (4) bytes, where (4) - byte

          displacement of 4 from the beginning of the file.
+ N [data] Packed animation frames. They

          are consistently and

          their format is similar to the format ZXF

          the above except

          lack of signatures, and version

          format, byte flags.

           Adding the address of the first byte

          Data in this section to each

          element in the table displacement (+6)

          we get a table of pointers to

          each frame of animation.


 As follows from the description of the format - this
format can not store more than 255
animation frames, or create animations
larger than 65535 bytes. But for the Speccy
it just right.
 Someone else might point out that here
spent essentially doing nothing as much as 4 bytes
deposited with the signatures and format version.
But if you think you can understand what
loss of 4 bytes, we get the opportunity to
accurately identify the file format. Same
BestView "knowing" the file format of this type
for each version will be able to get an accurate
information about its contents. And in the
demo can be kept small
manager, who is on the header format
able to determine - what the player needed
used for the animation and
asked each time to get into the code when
Change animation file.
 Now more about the meaning of each bit
in a byte of flags:
 At this point, the values ​​for
following bits:
 Bits 0 .. 2 - indicate the type of player to
this animation. The contents of these bits
determines which player you want to use
to play this animation.
 Possible values:
000 - Normal player.
001 - Interlace player. Differs from

      customary that displays an animation

      not on every line, and through one. In

      packed animation only

      difference from normal data will be

      that are saved only even

      or only the odd lines of source

      image depending on whether

      how important the Y coordinate

      upper-left corner of the frame.
010 - C64 player. This player uses

      method of deriving the images, which I

      I first saw on the C64. This method

      was first used by me in Deme

      Binary Love (early in the second part,

      where rotating cubes). This method

      gives the effect of "dissociation" pictures

      on screen and also allows

      short-change the image by 4 times

      smaller than the image on the screen.

      Accordingly, the only difference

      compressed data is that

      original image is compressed in the

      X and Y two times.
 Values ​​011 .. 111 at the moment until
not identified and reserved.
 I want to note that, in fact, these methods
differ only by the size of the image
so they are interchangeable and any player
can play an animation for any type of
players. Naturally only that after
unpacking another player image
will look compressed / stretched.

 Bit 3 - way conversion image.
If this bit is cleared - frames are packed with
recoding by rows if this bit
set - then use the recoding
columns. About these methods, recoding
I already wrote above. I will also say that
Currently there is only player to
animations with recoding the columns. This
due to the fact that, as I said,
This method gives a much greater degree
packaging. However, any player can be without
problems converted into use for
animations with recoding the rows.

 Bit 4 - way to compress the sequence
personnel. If this bit is 0, then staff
Animation compressed based on previous
frame. Ie before the compressed frames -
it is superimposed on XOR on the previous frame
and packed a result of this operation. If
as this bit is 1 - then the animation frames
packaged independently, each on its own.
One must also consider the point that
have staff that are packaged with the preceding
window size unpack, position and size
which is written in the header of each
frame will be different. For whatever
packed frame window will unpack
the same for all frames.
 At the moment there is only player to
regardless packed frames. This is due
that the existing algorithm depakera
effective only for such animations.
 Should also be noted that the value
this bit is only defined in ZXA files
ZXF files for this bit is undefined.
 The remaining bits in this flag for a given
version of the format is undefined and therefore
always dropped.

 Well, on the basis of these data
anyone can write a set of procedures for
packing and unpacking animations. All
Required information for this is described in
this article.
 But it's not all. In addition, in order to
to you it was easier to deal with all of this and
do not waste your time (which we all always
not enough) for something to write it all
own - I give you to study and
use their library to work with
These animations - ZXA library.
 Detail the use of components of this
library described in this article ZXA library, to
which I will now refer.