Inferno #07 31 мая 2005

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

Video - On packaging for a video ZX Spectrum.

                   On packaging for a video ZX



   Packaging video for the ZX is not needed when playing videos 
with IDE devices because their volumes are very large, and the 
rate of exchange with them high enough to add even a sound (for 
packaged Nogo as a complex issue of digital audio samples at a 
constant rate). But the ZX-distribute the program in large 
numbers Rea flax only on floppy disks, which gives its 
limitations: the program should have a modest size, estimated 
from a fraction of floppy disks to 3 diskettes and videos to, 
respectively, to pack. Especially need to pack clips to the 
small programs - such as newspapers. After all, absurd to hold 
the roller more than half of the release. 


               The general idea of ​​packing for familiarity


   Intuitively, in a video store need only
changing places, but how to encode the place has changed, and
what is not? Trivial XOR frame to frame no gain in
uncompressed size does not, except in archives.
Accordingly, the idea to somehow mark the altered cells
point, of course, size is not a pixel, and, say, 8x8 pixels -
familiarity to operate very comfortably. The idea is as old as 
the hills, she were used in Yekaterinburg Bomber'e and is 
described in SC someone primeval room Plutonium'a.


   Naturally, this video screen is just "breathe", the picture
varies throughout the area. Therefore, we must remember not all 
of menivshiesya familiarity, but only those that have changed 
greatly. That is the difference between the current image in 
the familiarity and desired image is more than N pixels, or 
greater than N color gradations, counted as 4 · dG +2 · dR + dB 
(where dG, dR, dB - errors on the color components). Basically, 
I used another formula of the error: 2 · dG + dR + dB, the 
result was not worse. 

   The main issue in this method: how to store information
mation about what familiarity changed? Sometimes changed
familiarity are groups that are sometimes scattered.


                       Managing the flow


   To do this, create a control flow or set spetskodov, VNO
simy in the video. The first is better, since (see also this
below), the flow characteristics of familiarity and flow, which 
describes the geometric metry of the picture (in which whatever 
form) is significantly different Ny, which affects the degree 
of compression of the future of these threads (now we engaged 
in encryption and compression result of loans later). 

   'll Let you know immediately the best found through 
experiments ACT  proper coding:


  1. Black / white video:
0 .. 84 - skip 0 .. 84 familiarity, a new - non-standard;
85 .. 169 - 0 .. 84 to miss familiarity, the new - standard;
 170 .. 254 - 0 .. 84 to miss familiarity, the new - 0-e 
standard 

                                                       (Blank);
 255 - end of the frame.

  2. For color video:
 0 .. 54.55 .. 109 - Attribute # 01 .. # 37, # 41 .. # 77. 
Nonstandard 

                                                     
familiarity;  110 .. 164.165 .. 219 - Attribute # 01 .. # 37, # 
41 .. # 77. Standard 

                                                     
familiarity; 220 .. 255 - 1 .. 36 missing familiarity.


   The fact that such a standard and nonstandard, I'll tell 
below, be patient ...



              How to get a set of frames from video


   Although almost all the videos have the same extension. Avi
or. mpg, inside of them can be used dozens of different methods
Dov compression. None of them is not universally accepted 
standard. Developers compression methods spread their CODECs 
(encoder decoder) in the form of drivers for Windows. 
Accordingly, the user often should before watching a new movie 
slazit to internet and download new versions of codecs. Players 
even have the audacity to climb over those in the 'Net without 
a demand. Some codecs are claimed as new older versions do not 
play clips of old versions, so sometimes have to juggle these 
codecs, reinstalling one version after another.


   Paranoid capitalists have organized two "standard" code
Cove. One variant encodes for a patient on-screen con
text, which could not take a screenshot (see that no
infringe copyright or authors of the film). These codecs uses 
one hundred ndartny Windows Media Player. Another option (it is 
probably to Roger, but we have the structure of stripping for 
this money to organize yet not yet) decodes the array (which 
displays the player alone), which allows user to remove the 
snapshot, but about gram - to record a video frame by frame.


   Naturally, we need a second option.

   Further, the required Virtual Dub. No video editors with 
boundary sivym interface, in practice, no good - there is no Vyg

manual ultrasonic frame by frame, and a very limited number of 
filters. Virtual Dub - a small and powerful program that does 
not suffer from these inadequate tkami. True, she 
poglyuchivaet: saves the sequence ka firewood is not a 
specified directory, and in those where the last conserved 
nyali avi; instead bmp can save a strange format, associated 
LIMITED with the used method of compression (and therefore 
before they are stored on sequence frame compression must be 
disabled). However, the perturbation zhno that at least the 
first bug relates to one specific version.


   Before unloading frame by frame (save image sequence) you 
must  the following steps:


   1. Remove unnecessary snippets of film;

  2. Add filter null transform, framing the picture (the cutoff
zayuschy frame) to the shot did not get the black boxes at the 
top and bottom (These are) or any "proprietary" emblem in the 
corner (These too are: that the capitalists - the paranoid, I 
have said above. Incidentally, this is a mental disorder - the 
label kopiraytomaniya - in my experience, a highly contagious 
and extremely  extremely difficult to cure).


  3. Add a filter, image scaling: it is best to
 width was 256 pixels, height - any.

  4. To taste add blur the picture in time, such
filters there are two types: motion blur (2 adjacent 
superimposed frame) and temporal smoother (superimposed to 4 
different images, and the effect of power adjustable). This is 
especially needed in the If the picture "jumps" brightness 
(drawing the Soviet Cartoon or very old film).


   Note that the unloading frame by frame requires many 
megabytes disco phase space, do not be greedy - thousands of 
shots you'll probably all second, to anything, quite a few 
hundred. 

   Shiru Otaku suggested as possible get shots without
Virtual Dub (young protsedurkami in C).


   You indicates the number of frames in a film that takes a 
buffer, which causes vaesh decoder - you get shot. A few lines 
of code. 

# Include <vfw.h>
 / / # Pragma comment (lib, "vfw32.lib") / / this is the 
standard Lieb, can 

     / / Just to the project to include, you may (in msvc) via 
pragma ... 

AVISTREAMINFO vzx_pstream;
PAVISTREAM vzx_avi;
PGETFRAME vzx_frame;

 int vzx_width, vzx_height, vzx_msek, vzx_allframes; / / 
settings form                            / / Deo, determined to 
open a file  char * vzx_data; / / pointer to memory in which to 
shove data 

                               / / (Do not forget to allocate 
this memory!) 

   open the file:

AVIFileInit ();
 if (AVIStreamOpenFromFile ('vzx_avi, szFile, streamtypeVIDEO, 
0, 

  OF_READ, NULL)! = 0) / / did not work to open the file
 AVIStreamInfo (vzx_avi, 'vzx_pstream, sizeof (vzx_pstream));
 vzx_width = vzx_pstream.rcFrame.right-vzx_pstream.rcFrame.left;

                                                  / / Width of 
the frame  vzx_height = 
vzx_pstream.rcFrame.bottom-vzx_pstream.rcFrame.top; 

                                                  / / Height of 
the frame vzx_allframes = AVIStreamLength (vzx_avi); / / how 
many frames  vzx_msek = AVIStreamSampleToTime (vzx_avi, 
vzx_allframes) /  vzx_allframes; / / how many milliseconds per 
frame (here know and fps) vzx_frame = AVIStreamGetFrameOpen 
(vzx_avi, NULL); if (vzx_frame == NULL) / / did not work to 
open a frame from a file (for example, 

                                                   / / Codec is 
not present) 

   reading frame:

LPBITMAPINFOHEADER lpbi;
 lpbi = (LPBITMAPINFOHEADER) AVIStreamGetFrame (vzx_frame,

                                                   frame 
number);  vzx_data = (char *) lpbi + lpbi-> biSize + lpbi->


  biClrUsed * sizeof (RGBQUAD); / / Get a pointer to memory 
where 

           / / Is decoded frame as rgbquad - r, g, b, 0



   close the file:

AVIStreamGetFrameClose (vzx_frame);
AVIStreamRelease (vzx_avi);
AVIFileExit ();



   Actually, that's all. Nothing complicated.



                      Conversion to ZX Screen


   Since there are different kinds of drawing video frames (se
ICA, large or small parts with good or poor illumination
generalization of, outline cartoon-rendered animation ...), 
susches exist a raznichnye and quality criteria for transfer of 
images to ZX. 

   I first converted a rather exotic algorithm has
yuschim even a parameter suppression ochankovki (similar to 
bright, applied at the stage of dithering). But later, after 
writing a concentration vertora static screens, I took the 
algorithm is already out of it (ordered / diamond option - 
because the Floyd-Steinberg is not suitable for stacking 
forging). About this converter and its algorithm, I will write 
another article.


   Of course, had to make some distinctions.

   Apparently, it is necessary to prohibit the use of 
complementary colors (Whose sum is white) as attributes of 
familiarity (Except ink = 7, paper = 0). Artists are virtually

do not apply, and their constant peremargivanie with b / w (PC
will not be able to understand that better, even with small 
changes video frame) is nothing good for packing will not. 
Similarly, with red-green and red and blue familiarity.


   The use of familiarity in one color, differing only in system
her part, definitely need to ban such subtleties practice
practically not noticeable in the video.


                     Standard familiarity



   4 bytes on familiarity - too extravagant, given the
the fact that familiarity can often be very similar risun
ki. I would like to encode at least one half of familiarity buy
vol. How?

   Initially, I drew nine uniformly primed familiarity from
black to white. It is logical. They are indeed often used
zuyutsya.No in the amount of the roller they do not cover even 
half of all familiarity, so it was necessary to draw more.


   The first idea was - to automate this process.

   At that time I requested Slip'a tried to make a video for u
algebra and a screen saver with a military plot. I got the 
fragments of phi lma "Wild Wild West" ("Wild Wild West"). Slip 
allow ISPO lzovat 256k, and I wanted to implement a longer 
movie. On the time has not yet ochankovyvalos video (see next 
Glaucus) because I have not yet invented a way to generate 
translation tables 2 bytes to 1. Accordingly, non-standard 
familiarity occupied much as 8 bytes.


   I have included a 9 standard familiarity in the flow of 
non-standard (app zeal in the top row familiarity to use a few 
rare codes like% 10100101, what is the limitation on the eyes 
discreetly) and ogranizoval another 1-byte code for which was 
consequently vat number familiarity in the ring list. Circular 
list soda whinnying 256 familiarity, was initially empty, and 
only replenished nonstandard familiarity encountered in the 
stream. If the packing schik find similar (not necessarily 
identical - the difference could up to 6 pixels) familiarity in 
a circular list, he put in Stream this tricky code and number.


   That video was of poor quality and did not go into the game, 
its 128k option still lies on my disks in assembled form.


   What are the errors of this method? Why was he during backup 
gives If  SHKOM greater length of the file?


  1. Become a standard set of familiarity, not enclosing
yuschie the entire range of the most common forms of 
znakomest.Oni generally speaking slit obtained almost by 
accident, and useful familiarity may do not get to the list 
(they could inadvertently be replaced by the UPA forged on some 
rough and hairy familiarity, featuring  seanmcsean to 6 pixels).


  2. Standard codes and numbers of familiarity in a circular 
list of fall into the same stream as a byte unusual 
familiarity. And are very different mathematical properties! 
For example, the number in the circular list - the number of 
evenly distributed. A code Standard familiarity is not enough 
that is made from one distribution leniya frequencies bytes - 
two distributions (for the upper byte and for everyone else) - 
but also destroy the structure of the flow of these most bytes, 
because of what the LZ compression can be very, very loose  in 
force. 

  3. In this video you can not loop the bits you want - because
that the state of the ring list in the first and second pass 
will  children differently.


  4. The very idea of ​​a stream of bytes will not do - for 
example, even bytes are distributed quite as odd. Vitamin Pos

also suggested naXORivat adjacent bytes on each other, with
uniform shading into a sequence identical
Output bytes.


                           Ochankovka


   I decided to go for the more difficult path: to find 256 
standard pairs of bytes (lower-upper) to any pair of bytes can 
be had from some are not very big mistake lead to a standard

GOVERNMENTAL. Generally it is a very promising trend: for 
example, so you can pack big sprites in the games, they will 
become a factor of 2 smaller in size and thus will not be 
displayed slowly. 

    Made as follows:

  1. Hatched the picture turns into chunks 2x2 (the eye is 
almost  unnoticed, if not thin lines).


  2. Sort the 625 possible combinations of chunks of 
frequencies encountered numbers on any video or picture (the 
result will be used  vatsya for other pictures and videos).


  3. Starting with the rarest, to screen out those combinations 
that almost coincide with any other combination (different

 one pixel · gradation).

  4. Of the remaining weeds out those who are different from a 
no whether different combinations of the two pixel · gradations.


   As a result, reserve 2 tables: one for encoding (from
625-variant combinations of counts in the 256-variant), the 
second for decoding (of the 256 options are converted into 2 
bytes). 

   Both are in the appendix.

   First - Code256.dat. Changes of left chunks correspond
large changes in number combinations, there is need to use
multipliers 125, 25, 5 and 1 for the gradation of the left, 
middle and right chunks, respectively.


   Second - deco256.C. It lies across the lower bytes 256 bytes
After the top. Also attached the source intro to the magazine 
(where video is encoded without compression (entropy coding) in 
Half fmanu, so that the program is short and straightforward).



                       Huffman compression on


   Perhaps the direction of saving: saving memory and ekomoniya 
ME hundred on the disk. If the movie is short, it is better to 
keep in mind Uncompressed Size (without compression Huffman), 
and on disk - in Rar. So killed two hares: video takes up less 
space on the disk and less slow when playing. But if it is 
long, you and the PA myati be stored compressed by Huffman. A 
compressed by LZ is better not to store - he needed to unpack 
the box, so the gain in compression TII "compensated for" loss 
of memory for the needs of the window. And we all memory as 
possible, assigned to the video storage. If movie extra-long 
(with podgruzku) to be used, and LZ. 

   Compressed video stream for Huffman I used in the video 
Dimon128 (C ParaDIGMus'03). This video, I was preparing 
simultaneously for writing ZXRar, so packer for Huffman, I was 
in isho dnike. The flow of "standard" familiarity in this video 
is not packed (He did not pack the), an attribute as well 
(although it would be packed in 2 times).


   ZXRar can, unlike his prototype ptsshnogo, packing
pure Huffman, without departing from the format for this Rar. 
For this check box LZ-method is 0 k. In this stream, the NAM

Example for our intro is compressed better than the present 
method Rar. If we use LZ, we recommend the processing of sign

places no rows, and columns - so compression is more efficient! 
I'm so made in the converter, and in the intro, though without 
LZ is not necessary - only slow decompression.



                  Again, familiarity standard


   So I finally knocked the idea of ​​what familiarity
should be standard. Tsvetoperehody!

   Tsvetoperehody in 16 directions, between 5 major grades
Gray, on 3-5 key positions from the center of familiarity - 
they do not so much!


   Initially, I drew 512 familiarity, not counting the nine 
old. Sde lal I is for bmp-image by placing familiarity (4x4) 
grid with an interval of 1 pixel between familiarity.


   It is clear that many (not immediately predskazhesh which) 
of these rice nkov used so rarely that you store them in 
unpacker unprofitable (1 character in the Huffman tree takes 4 
bytes, and very familiarity - 4 ochankovanno-zadokirovannyh "or 
8 normal bytes, while the yields, after winning package 
somewhere 2 bytes each occurrence - hence the need to not less 
than 5.7 occurrences for some benefits).


   But how to figure out which ones are superfluous?

   Thought: familiarity can not be used, a) if such form
generally unpopular, and b) if this form is rare in a specific
dimensional video, and c) if all such drawings advantageous to 
transmit close shape znakomentami.


   Some familiarity, the resulting strong (less than 4 pixels
fishing · gradation difference) similar to the other set of 
familiarity, I immediately marked red spots underneath.


   Trying to apply all the packer and familiarity count
for each of them the number of matches, displayed on the 
screen, which of them are rare. After that we remove the rare 
familiarity with pictures (Whole groups of symmetry, since the 
transition to the left, right, up and down should be equally 
likely in the long run). Point her, drags them to the periphery 
of bmp - then suddenly come in handy? Next, restart our video 
converter, drives on the same ro Lika, consider the length of 
the output streams in packed form Rar'om - won or lost? - 
statistics and familiarity. Remove rare, return the remote, if 
mistaken in the assumption of their nevygo dnosti again restart 
the converter, and so on. Minimum objective - Get <= 256 
familiarity, the task is the maximum - you get the most 256 
qualified familiarity (or less than 256, if less profitable). 

   I wanted to get exactly 256 standard familiarity, but not 
published - To select the most useful (the least useless) from 
the heap discarded too long to sort out some of the different

videos, I have no such amount of free time. A
payoff will be - kopek, somewhere around 1-2 percent at the most
optimistic assessment of ... Similar percentages, if not
Out of memory, it's easier to win by imperceptible to the eye 
Snee tion quality video, which came up with policy settings

conversion.

   Comparing the results on several videos, I threw it all
occupation - the search for effective standard familiarity - as
types of images is a huge amount. Just in case I
just added (to the standard familiarity was 256) in the set
familiarity for contour animations (the white lines on black 
background). Packing such rollers needed (see below about the 
settings) with parameters ramie: standard error dots = 9; and 
standard error, respectively, 4.9 = 36.



                      Conversion strategy


   Error reporting, as I said, it's best to consider
the formula: oshibkasinego + + oshibkakrasnogo oshibkazelenogo 
· 2. Can with coefficients 1, 2 and 3, respectively, can be 1, 
2, 4, correspondingly Twain.


    Standard familiarity is beneficial if:

        oshibkastandartnogo-oshibkanestandartnogo  
StErLevel (Slightly lower quality in fast motion)


   else if
starayaoshibka> BadErLevel [, delay> BadDelay (little delay)]
(Main branch, the same simple method of packaging. Maybe a 
little keep up the branch with the standard familiarity)


   else if
starayaoshibka> GoodErLevel, delay> GoodDelay (long delay)
(Erase small defects on the slow motions)

   else if
New - Standard (starayaoshibka-error)> 0, delay> ClDelay
(Erase individual pixels, which remained on a solid background 
- their does not relieve any other branch of the algorithm).



         Setting Recommendations Strategy


   You can not ask for the familiarity of standard margin of 
error below than for "good" familiarity. Because of this "good" 
would simply transfer hvatyvat of familiarity that could be 
encoded standard (ie shorter). When the conversion of the 
cartoon Uncle Theodore had to remove the constant change of 
color of the walls (Because it is drawing a cartoon). For this 
I used a Virtual Dub temporal smoother filter with parameter 9, 
and its converter set both limits the level of 20 (and for the 
"bad" - 50). Delay for "good" put 1 for "bad" - 0, and "pixels" 
(remember, "Pixels" - it is also standard familiarity, but 
without the limit errors - removes stray pixels, the filter is 
not in Video Stu dio) - 9. The average volume of the image even 
without packing up 240 bytes (including packaging - 150). This 
is despite the ban on bright white. And with him (So ​​the 
picture seems bigger) - 285 and 200 bytes per frame according 
tstvenno. 

   You can ignore the fact that the errors in the periphery 
than replacing tny than in the center. How to make use of it, 
decide for yourself: you can increase the delay (delays) away 
from the center (the distance can be roughly calculated as the 
sum of dx + dy, where dx and dy - the distance from the center 
of resp. axis of familiarity), and can be away from Centre to 
raise the limits on the error. I experimented with it on 
rollers in the final cut'e Wolf'2004, but it is not suitable 
for all videos.



                How to connect all the threads in one


   Store 3 separate flow inconvenient: they are difficult to 
drive in page (you have to start with non-circular addresses, 
ie, cut files byte by byte) and when you play the page 
constantly clicked. If they do not click, the performance was 
video player would be greater.


   Immediately rejects the idea of ​​a flow generated by 
another hundred packing stage (followed by the file compression 
rar'om). Because is a pure loss - a mixture of heterogeneous 
flows with different Mi properties packed worse than these 
streams separately. Following Therefore, it is necessary to 
alternate the bytes (or bits) of the three already compressed 
streams. To build such a leapfrog need a separate program, it's 
best as a source. If the alternate is bits, the extractor will 
be shorter - you can use one and the same procedure, the sample 
bits for all the threads together to keep shifted the current 
byte in the same A '(see the description of the decay 
kovschikov Hrust in IG # 5), and indeed, even for the Huffman 
decoder account of the use of only one.



               Recommendations for video playback


   Information on the frame for the average color video with a 
slowly moving camera is unpacked about 500

bytes, assuming that all 4 threads: Manager / an attribute, and 
chankovy znakomestny. This means that in a well-packaged, we

3.5 MHz will be able to play up to 20 fps (the most convenient 
implementation Deco coding of Huffman decodes up to 10 k / s). 
Selected speed play to maintain a constant average, compute

account the frames (for IM 1 - a system variable FRAMES: 
23672/3/4, for IM 2 can easily implement the same). Realized 
this synchronization by writing to 23,672 the number 0, 
followed by controlled field will get there at the end of the 
construction of the frame number (call is the number of M). If 
it's (M) less than a given N (N = 5 to 10 fps), then forward to 
a specified (ie, up to 5). If more than this - that frame had 
not yet arranged for the right time (maybe he was "the key 
Howl: changed the whole picture), and the next cycle should 
instead zero write to 23672 the number of MN. Here is a snippet 
(in the end  processing frame):


         LD A, (23672) <

         SUB N

         JR C,

         LD (23672), A

   0 we must enter only at the beginning of the video player to 
cycle frame processing.


   Clock source can also be a drive with him if
constantly being Podgruzka (as in the movie "Locomotion" or demo
"Power Up"). The size of the packaged image even theoretically 
possible to customized to a fixed number of sectors - although 
it is very difficult. 

   If the memory is not enough, the first frame can be shipped 
directly to screen, and then run the video from the next frame. 
Still, the pair kilobytes on the road is not lying. But on the 
drive such a video will same space.


   My packer (for Delphi) - this is not a release, but a purely 
experimental imental thing, after my explanation you will be 
able to write the same. Still, putting the source code in an 
application - it is better Change in finished, why waste time 
writing that already been written?


   But the limits of experimentation not - I do not fully 
implement even its ideas package (for example, there is not 
even a simple scrolling which is required for many 
commercials), you may be singing the same curl even more 
interesting ideas. 

   If you come up with something good - write to us ...

A. Coder