Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revision Previous revision
dev:devmanual [2006/07/16 09:58]
stockholm
dev:devmanual [2006/07/16 10:01] (current)
stockholm
Line 512: Line 512:
  
 ==== Boot prom entry points ==== ==== Boot prom entry points ====
 +(gk)As mentioned above the net boot process has to provide interrupt 78h as an entry point in case, the returnable flag (bit 9 of the flags field in the image header) of the boot image has been set. When calling this interface interrupt, the caller has to load the AH register with a value indicating the type of operation requested: ​
 +<​file>​
 +00h  -  Installation check
 +        Input: ​ none
 +        Output: AX  -  returns the value 474Bh
 +                BX  -  flags indicating what further services are
 +                       ​provided by the net boot program:
 +                        Bit 0 - packet driver interface (see below)
 +                        Bits 1 to 15 are unused and have to be zero
 +
 +01h  -  Cleanup and terminate the boot process services. This will
 +        also remove the services provided by interrupt 87h.
 +        Input: ​ none
 +        Output: none
 +</​file>​
 +   ​Further functions are not yet defined. These functions are only available to boot images which have the first magic number at the beginning of the image header, and have the returnable flag set in the flags field. ​
 +
 +In order to provide compatibility with net boot programs written to match an earlier version of this document, the loaded image should check for the existence of interrupt 78h by looking at it's vector. If that's 0:0, or if it does not return a proper magic ID after calling the installation check function, the boot image has to assume that the net boot program does not support this services interrupt. ​
 +
 +If the bit 0 of register BX of function 00h is set, the boot program has to provide a packet driver interface at interrupt 79h as described in the packet driver interface standard, version 1.09, published by FTP Software, Inc., which is not repeated here. It serves as an interface to the system'​s network card. It is important to note that the net boot process has to provide a clean packet driver interface without any handles being defined when the boot image gets started. It is expected that the boot image sets up it's own TCP/IP or other network'​s stack on top of this packet driver interface. When the boot image returns to the net boot process, it has to return a clean packet driver interface as well, without any handles being defined.(gk)
 +
 ==== Example of a boot image ==== ==== Example of a boot image ====
 +Here is an example of how the boot image would look for Linux: ​
 +<​file>​
 +  0x1B031336, ​ /* magic number */
 +  0x4,         /* length of header is 16 bytes, no vendor info */
 +  0x90000000, ​ /* location in ds:bx format */
 +  0x90000200, ​ /* execute address in cs:ip format */
 +
 +               /* 2048 setup.S bytes */
 +  0x4,         /* flags, not end, absolute address, 16 bytes this
 +                  record, no vendor info */
 +  0x90200, ​    /* load address - note format */
 +  0x800, ​      /* 4 8 512 byte blocks for linux */
 +  0x800,
 +
 +               /* kernel image */
 +  0x4,         /* flags, not end, absolute address, 16 bytes this
 +                  record, no vendor info */
 +  0x10000, ​    /* load address - note format */
 +  0x80000, ​    /* 512K (this could be shorter */
 +  0x80000,
 +
 +               /* ramdisk for root file system */
 +  0x04000004, ​ /* flags = last, absolute address, 16 bytes this
 +                  record, no vendor info *//
 +  0x100000, ​   /* load address - in extended memory */
 +  0x80000, ​    /* 512K for instance */
 +  0x80000,
 +               /* Then follows linux specific information */
 +</​file>​
 +
 ==== Terms ==== ==== Terms ====
 +When I say 'the net boot process',​ I mean the act of loading the image into memory, setting up any tables, up until the jump to the required location in the image. ​
 +
 +The net booting program executes the net boot process. The net boot program may be a rom, but not neccassarily. It is a set of instructions and data residing on the booting machine. ​
 +
 +The image, or boot image, consists of the data loaded by the net boot process. ​
 +
 +When I say 'the PC boot process',​ I mean the general PC rom bios boot process, the setting up of hardware, the scanning for adaptor roms, the execution of adaptor roms, the loading in of the initial boot track. The PC boot process will include the net boot process, if one is present. ​
 +
 +When I say client, I mean the PC booting up. 
 +
 +When I say 'image host', I mean the host where the boot image is comming from. This may not have the same architecture as the client. ​
 +
 +The bootp protocol is defined in RFC951 and RFC1084. The tftp protocol is defined in RFC783. These are available on many sites. ​
 +
 +A bootp server is the machine that answers the bootp request. It is not neccessarily the image host. 
 +
 +"​Can"​ and "​may"​ means doesn'​t have to, but is allowed to and might. "​Must"​ means just that. "​Cannot"​ means must not.
 ==== References ==== ==== References ====
 + ​Stevens,​ W.R 1990, Unix Network Programming,​ Prentice Hall, Englewood Cliffs, N.J., 1990
 ===== Appendix B. Compression algorithm, 1 July 1997 ===== ===== Appendix B. Compression algorithm, 1 July 1997 =====
 +Markus Gutschke, gutschk AT math PERIOD uni-muenster PERIOD de 
 +
 +The compressor achieves an average compression rate of 60% of the original size which is on par with "​gzip"​. It seems that you cannot do much better for compressing compiled binaries. This means that the break even point for using compressed images is reached, once the uncompressed size approaches 1.5kB. We can stuff more than 12kB into an 8kB EPROM and more than 25kB into an 16kB EPROM. As there is only 32kB of RAM for both the uncompressed image and its BSS area, this means that 32kB EPROMs will hardly ever be required. ​
 +
 +The compression algorithm uses a 4kB ring buffer for buffering the uncompressed data. Before compression starts, the ring buffer is filled with spaces (ASCII character 0x20). The algorithm tries to find repeated input sequences of a maximum length of 60 bytes. All 256 different input bytes plus the 58 (60 minus a threshold of 2) possible repeat lengths form a set of 314 symbols. These symbols are adaptively Huffman encoded. The algorithm starts out with a Huffmann tree that assigns equal code lengths to each of the 314 symbols (slightly favoring the repeat symbols over symbols for regular input characters),​ but it will be changed whenever the frequency of any of the symbols changes. Frequency counts are kept in 16bit words until the total number of compressed codes totals 2^15. Then, all frequency counts will be halfed (rounding to the bigger number). For unrepeated characters (symbols 0..255) the Huffman code is written to the output stream. For repeated characters the Huffmann code, which denotes the length of the repeated character sequence, is written out and then the index in the ring buffer is computed. From this index, the algorithm computes the offset relative to the current index into the ring buffer. Thus, for typical input data, one would expect that short to medium range offsets are more frequent than extremely short or medium range to long range offsets. Thus the 12bit (for a 4kB buffer) offset value is statically Huffman encoded using a precomputed Huffman tree that favors those offset values that are deemed to be more frequent. The Huffman encoded offset is written to the output data stream, directly following the code that determines the length of repeated characters. ​
 +
 +This algorithm, as implemented in the C example code, looks very good and its operating parameters are already well optimized. This also explains why it achieves compression ratios comparable with "​gzip"​. Depending on the input data, it sometimes excells considerably beyond what "gzip -9" does, but this phenomenon does not appear to be typical. There are some flaws with the algorithm, such as the limited buffer sizes, the adaptive Huffman tree which takes very long to change, if the input characters experience a sudden change in distribution,​ and the static Huffman tree for encoding offsets into the buffer. The slow changes of the adaptive Huffman tree are partially counteracted by artifically keeping a 16bit precision for the frequency counts, but this does not come into play until 32kB of compressed data is output, so it does not have any impact on our use for "​etherboot",​ because the BOOT Prom does not support uncompressed data of more then 32kB (c.f. doc/​spec.doc). ​
 +
 +Nonetheless,​ these problems do not seem to affect compression of compiled programs very much. Mixing object code with English text, would not work too well though, and the algorithm should be reset in between. Actually, we might gain a little improvement,​ if text and data segments were compressed individually,​ but I have not experimented with this option, yet.
 ===== Appendix C. Copying conditions of the compression code, 1 July 1997 ===== ===== Appendix C. Copying conditions of the compression code, 1 July 1997 =====
 +Markus Gutschke, gutschk AT math PERIOD uni-muenster PERIOD de 
 +
 +The compression code as implemented in "​lzhuf.c"​ was taken from a BBS program written by Joachim Schurig <​jschurig AT zedat PERIOD fu-berlin PERIOD de>. He states that the code can be used freely for programs that are covered by a "​freeware"​ license. This probably includes both BSD style licenses and the GPL. 
 +
 +The code in "​zloader.asm"​ is a reimplementation of the uncompressor. It has been written from scratch and is hereby placed under the conditions of the GNU General Public License (GPL). The algorithm is outlined in Appendix B. 
 +
 +Thus, there are no copyright problems with using this code, but there still might be difficulties with software patents. These patents are not legal in most parts of the world, but if you live in a country that honors software patents then you should verify that using these algorithms is legally permitted. Unless you are absolutely sure, that there are no legal obstacles, you should use the code for educational purposes only (this assumes that your educational institution is exempted from patent laws). The author cannot be held responsible for using the program code in violation of applicable local laws. 
 +
 +If you are aware of patents that might affect the legality of using the code in some parts of the world, please let me know. 

QR Code
QR Code dev:devmanual (generated for current page)