Writing a simple UDP server in Ada for a STM32F746 ARM controller is now easy with the use
of the Ada Embedded Network stack.
The article describes through a simple UDP echo server the different steps for the implementation
of an UDP server.
The Echo server listens to the UDP port 7 on the Ethernet network and it
sends back the received packet to the sender: this is the RFC 862 Echo protocol.
Our application follows that RFC but it also maintains a list of the last 10 messages
that have been received. The list is then displayed on the STM32 display so that
we get a visual feedback of the received messages.
The Echo server uses the DHCP client to get and IPv4 address and the default gateway.
We will see how that DHCP client is integrated in the application.
The application has two tasks. The main task loops to manage the refresh of the STM32
display and also to perform some network housekeeping such as the DHCP client management and
ARP table management. The second task is responsible for waiting Ethernet packets, analyzing them to handle ARP, ICMP and UDP packets.
Through this article, you will see:
How the STM32 board and network stack are initialized,
How the board gets an IPv4 address using DHCP,
How to implement the UDP echo server,
How to build and test the echo server.
STM32 Board Initialization
First of all, the STM32 board must be initialized. There is no random generator available in the
Ada Ravenscar profile and we need one for the DHCP protocol for the XID generation. The STM32
provides a hardware random generator that we are going to use. The Initialize_RNG must be
called once during the startup and before any network operation is called.
We will use the display to list the messages that we have received. The Display instance
must be initialized and the layer configured.
STM32.Board.Display.Initialize_Layer (1, HAL.Bitmap.ARGB_1555);
Network stack initialization
The network stack will need some memory to receive and send network packets.
As described in Using the Ada Embedded Network STM32 Ethernet Driver, we allocate the memory by using the SDRAM.Reserve function and the
Add_Region procedure to configure the network buffers that will be available.
An instance of the STM32 Ethernet driver must be declared in a package. The instance must be
aliased because the network stack will need to get an access to it.
NET_BUFFER_SIZE : constant Interfaces.Unsigned_32 := Net.Buffers.NET_ALLOC_SIZE * 256;
Ifnet : aliased Net.Interfaces.STM32.STM32_Ifnet;
The Ethernet driver is
initialized by calling the Initialize procedure. By doing so, the Ethernet receive and transmit
rings are configured and we are ready to receive and transmit packets. On its side the Ethernet driver will also reserve some memory by using the Reserve and Add_Region operations. The
buffers allocated will be used for the Ethernet receive ring.
The Ethernet driver configures the MII transceiver and enables interrupts for the receive and
Getting the IPv4 address with DHCP
At this stage, the network stack is almost ready but it does not have any IPv4 address.
We are going to use the DHCP protocol to automatically get an IPv4 address, get the default
gateway and other network configuration such as the DNS server.
The DHCP client uses a UDP socket on port 68 to send and receive DHCP messages.
Such DHCP client is provided by
the Net.DHCP package and we need to declare an instance of it. The DHCP client is based on
the UDP socket support that we are going to use for the echo server. The DHCP client instance
must be declared aliased because the UDP socket layer need to get an access to it to propagate
the DHCP packets that are received.
Dhcp : aliased Net.DHCP.Client;
The DHCP client instance must be initialized and the Ethernet driver interface must be passed
as parameter to
correctly configure and bind the UDP socket. After the Initialize procedure is called, the DHCP
state machine is ready to enter into action. We don't have an IPv4 address after the procedure returns.
The DHCP client is using an asynchronous implementation to maintain the client state according
to RFC 2131. For this it has two important operations that
are called by tasks in different contexts. First the Process procedure is responsible
for sending requests to the DHCP
server and to manage the timeouts used for the retransmissions, renewal and lease expiration.
The Process procedure sends the DHCPDISCOVER and DHCPREQUEST messages.
On the other hand, the Receive procedure is called by the network stack
to handle the DHCP packets sent by the DHCP server. The Receive procedure gets the
DHCPOFFER and DHCPACK messages.
Getting an IPv4 address with the DHCP protocol can take some time and must be repeated continuously
due to the DHCP lease expiration. This is why the DHCP client must not be stopped and should
Refer to the DHCP documentation to learn
more about this process.
UDP Echo Server
Logger protected type
The echo server will record the message that are received. The message is inserted in the list
by the receive task and it is read by the main task. We use the an Ada protected type to
protect the list from concurrent accesses.
Each message is represented by the Message record which has an identifier that is unique
and incremented each time a message is received. To avoid dynamic
memory allocation the list of message is fixed and is represented by the Message_List array.
The list itself is managed by the Logger protected type.
type Message is record
Id : Natural := 0;
Content : String (1 .. 80) := (others => ' ');
type Message_List is array (1 .. 10) of Message;
protected type Logger is
procedure Echo (Content : in Message);
function Get return Message_List;
Id : Natural := 0;
List : Message_List;
The Loggerprotected type provides the Echo procedure to insert a message to the list
and the Get function to retrieve the list of messages.
The UDP Echo Server uses the UDP socket support provided by the Net.Sockets.UDP package.
The UDP package defines the Socket abstract type which represents the UDP endpoint.
The Socket type is abstract because it defines the Receive procedure that must be
implemented. The Receive procedure will be called by the network stack when a UDP packet
for the socket is received.
The declaration of our echo server is the following:
type Echo_Server is new Net.Sockets.UDP.Socket with record
Count : Natural := 0;
Messages : Logger;
It holds a counter of message as well as the messages in the Logger protected type.
The echo server must implement the Receive procedure:
procedure Receive (Endpoint : in out Echo_Server;
From : in Net.Sockets.Sockaddr_In;
Packet : in out Net.Buffers.Buffer_Type);
The network stack will call the Receive procedure each time a UDP packet for the socket is received.
The From parameter will contain the IPv4 address and UDP port of the client that sent the
UDP packet. The Packet parameter contains the received UDP packet.
Implementing the server is very easy because we only have to implement the Receive procedure
(we will leave the Logger protected type implementation as an exercise to the reader).
First we use the Get_Data_Size function to get the size of our packet. The function is able
to return different sizes to take into account one or several protocol headers. We want to know
the size of our UDP packet, excluding the UDP header. We tell Get_Data_Size we want to get
the UDP_PACKET size. This size represents the size of the echo message sent by the client.
Having the size we truncate it so that we get a string that fits in our message. We then use
the Get_String procedure to retrieve the echo message in a string. This procedure gets from
the packet a number of characters that corresponds to the string length passed as parameter.
Packet.Get_String (Msg.Content (1 .. Len));
The Buffer_Type provides other Get operations to extract data from the packet.
It maintains a position in the buffer that tells the Get operation the location to read
in the packet and each Get updates the position according to what was actually read.
There are also several Put operations intended to be used to write and build the packet
before sending it. We are not going to use them because the echo server has to return the
original packet as is. Instead, we have to tell what is the size of the packet that we are
going to send. This is done by the Set_Data_Size procedure:
Here we want to give the orignal size so that we return the full packet.
Now we can use the Send procedure to send the packet back to the client.
We use the client IPv4 address and UDP port represented by From as the destination address.
The Send procedure returns a status that tells whether the packet was successfully sent or
Status : Net.Error_Code;
Endpoint.Send (To => From, Packet => Packet, Status => Status);
Now that the Echo_Server type is implemented, we have to make a global instance of it
and bind it to the UDP port 7 that corresponds to the UDP echo protocol. The port number must
be defined in network byte order (as in Unix Socket API) and this is why it is converted using
the To_Network function. We don't know our IPv4 address and by using 0 we tell the UDP stack
to use the IPv4 address that is configured on the Ethernet interface.
As explained in the overview, we need several tasks to handle the display, network housekeeping
and reception of Ethernet packets. To make it simple the display, ARP table management and DHCP
client management will be handled by the main task. The reception of Ethernet packet will be
handled by a second task. It is possible to use a specific task for the ARP management and
another one for the DHCP but there is no real benefit in doing so for our simple echo server.
The main loop repeats calls to the ARP Timeout procedure and the DHCP Process procedure.
The Process procedure returns a delay that we are supposed to wait but we are not going to
use it for this example. The main loop simply looks as follows:
Dhcp_Timeout : Ada.Real_Time.Time_Span;
delay until Ada.Real_Time.Clock + Ada.Real_Time.Milliseconds (500);
And the implementation loops to receive packets from the Ethernet driver and calls either
the ARP Receive procedure, the ICMP Receive procedure or the UDP Input procedure.
The complete implementation can be found in the receive.adb file.
Building and testing the server
To build the UDP echo server and have it run on the STM32 board is a three step process:
First, you will use the arm-eabi-gnatmake command with the
echo GNAT project. After successful build, you will get the echo ELF binary image in obj/stm32f746disco/echo.
Then, the ELF image must be converted to binary by extracting the ELF sections that must be put on
the flash. This is done by running the arm-eabi-objcopy command.
Finaly, the binary image produced by arm-eabi-objcopy must be put on the flash using the st-util utility. You may have to press the reset button on the board so that the st-util is able to take control of the board; then release the reset button to let st-util the flash the image.
To help in this process, you can use the Makefile and simply run the following make targets:
Once the echo application is running, it displays some banner with the information of the DHCP
state machine. Once the IPv4 address is obtained, it is displayed with the gateway and the DNS.
Take that IPv4 address and use the following command to send message and have them written on the
echo -n 'Hello! Ada is great!' | socat - UDP:192.168.1.156:7
(replace 192.168.1.156 with the IPv4 address displayed on the board).
The above message was printed with the following script:
while IFS='' read -r line ; do
echo -n "$line" | socat - UDP:$IP:7
done < $FILE
GID means Generic Image Decoder, a free, open-source library that can be found here.
The latest release features a couple of new application examples, among them a tool called Recurve for retrieving data from an image with plotted curves. Typically you come across a chart on a web site and would like to get the corresponding data, for reworking them in Excel - perhaps you want to spot specific values, or compare two curves that were not originally on the same chart, or use the data for further calculation. Sometimes the data is not available from the web site - and even less if the chart is from a PDF or a scanned newspaper page.
Fortunately, Recurve will do the painful job of retrieving the data points for you. It will detect gridlines and filter them out, then track the curves by matching their respective colours.
An example here:
Mortgage rates in Switzerland - 2004 to now. Chart is from the Comparis web site
GLOBE_3D Release 2016-07-05 - "Blender edition" Read more
GLOBE_3D is a GL Object Based 3D engine realized with the Ada programming language. URL: http://globe3d.sf.net
Use of Generic Image Decoder (GID) in GL.IO; now most image formats are supported for textures and other bitmaps to be used with GLOBE_3D (or any GL app)
New Wavefront format (.obj / .mtl) importer
Doom 3 / Quake 4 map importer more complete
Unified GNAT project file (.gpr), allowing to selected the target Operating System (Windows, Linux, Mac) and compilation mode (fast, debug, small) for demos, tools, etc.
Project file for ObjectAda 9.1+ updated
The first two points facilitate the import of 3D models from software such as Blender. Here is an example:
Click to enlarge
Coincidentally, the Wavefront file format so simple that you can also write 3D models "by hand" in that format. An example made in an Excel sheet is provided along with the importer, in the ./tools/wavefront directory.
Click to enlarge
GLOBE_3D: most image formats now available for textures Read more
The texture loader in GL.IO was around 15 years old and supported only the Targa (.tga) format for textures, plus a few sub-formats of Windows bitmaps (.bmp).
In order to make things easy when dealing with various models, e.g. those imported from Blender, the old code for reading images has been wiped out and the loader is using now GID for the job, supporting JPEG or PNG in addition. For instance the Blender model below is using the JPEG format for textures.
Futuristic Combat Jet (hi poly version) by Dennis Haupt (DennisH2010)
The following Blender model has a single PNG texture projected on a complicated surface called a Mandelbulb (never heard of before!) :
Mandelbulb 3D Panorama 3 by DennisH2010
GLOBE_3D is a GL Object Based 3D engine realized with the Ada programming language.
I have been slacking with Fedora AVR-Ada rpm binaries, but finally I found
some time to make new binary rpms. These binaries are for Fedora 25 (x86_64), which
will be released later in this month. I generated them on Fedora 25 (Server) Beta,
but they should work on the released Fedora 25 version also.
Like always, create file /etc/yum.repos.d/fedora-adalanguage.repo with contents:
name=Tero's Fedora RPM repository for Ada packages
sudo dnf install avr-ada --nogpgcheck
The used GCC version is 4.9.2.
Instead of using normal .spec files + rpmbuild, I build the binaries with my custom build script
and fpm (for installation, you need only dnf).
The installation happens to /opt/avr-ada-122
The RPMs are unofficial in every possible way and they are not endorsed by Fedora or AVR-Ada projects.
Zip-Ada v.52 - featuring LZMA compression Read more
Actually, these are two successive versions: v.51 with a basic LZMA encoder, v.52 with a more advanced one. The shift from v.50 to v.51 ensured 52 steps up in the Squeeze Chart benchmark, although the LZ part remained identical and the new "MA" part is a simple, straightforward encoder which comes in replacement of our sophisticated Taillaule algorithm for the Deflate format. This shows just how much the LZMA format is superior to Deflate. Then, from v.51 to v.52, there were 45 more steps upward. This is due to a combination of a better-suited LZ algorithm, and a refinement of the "MA" algorithm - details below.
* Changes in '51', 27-Aug-2016: - LZMA.Encoding has been added; it is a standalone compressor, see lzma_enc.adb for an example of use. - Zip.Compress provides now LZMA_1, LZMA_2 methods. In other words, you can use the LZMA compression with Zip.Create. - Zip.Compress has also a "Preselection" method that selects a compression method depending on hints like the uncompressed size. - Zip.Compress.Deflate: Deflate_1 .. Deflate_3 compression is slightly better.
The LZMA format, new in Zip-Ada on the encoding side, is especially good for compressing database data - be it in binary or text forms. Don't be surprised if the resulting archive represent only a few percents of the original data... The new piece of code, LZMA.Encoding, has been written from scratch. This simple version, fully functional, holds in only 399 lines, after going through J-P. Rosen's Normalize tool. It can be interesting for those who are curious about how the "MA" part of that compression algorithm is working. The code can be browsed here.
* Changes in '52', 08-Oct-2016: - UnZip.Streams: all procedures have an additional (optional) Ignore_Directory parameter. - Zip.Compress has the following new methods with improved compression: LZMA_3, Preselection_1 (replaces Preselection), Preselection_2. Preselection methods use now entry name extension and size for improving compression, while remaining 1-pass methods.
For those interested about what's happening "under the hood", LZMA.Encoding now computes (with floating-point numbers, something unusual in compression code!) an estimation of the predicted probabilities of some alternative encodings, and chooses the most probable one - it gives an immediate better local compression. Sometimes the repetition of such a repeated short-run improvement has a long-run positive effect, but sometimes not - that's where it's beginning to be fun...
The latest addition is an archive recompression tool.
AZip's recompression tool's results - click to enlarge
- Multi-document (should be familiar to MS Office users) - Flat view / Tree view - Simple to use (at least I hope so ;-) ) - Useful tools: - Text search function through an archive, without having to extract files - Archive updater - Integrity check - Archive recompression (new), using an algorithm-picking approach for improving a zip archive's compression. - Encryption - Methods supported: Reduce, Shrink, Implode, Deflate, Deflate64, BZip2, LZMA - Free, open-source - Portable (no installation needed, no DLL, no configuration file)
"Under the hood" features:
- AZip is from A to Z in Ada :-) - Uses the highly portable Zip-Ada library - Portablity to various platforms: currently it's fully implemented with GWindows (for Windows), and there is a GtkAda draft, but anyway the key parts of the UI and user persistence are generic, platform-independent
Software Serial for Adafruit Trinket (TX only) Read more
Some AVR devices, like attiny85 (on Adafruit Trinket, for example), do not
have hardware UART. However, it would be still nice to have serial output
I wrote a simple Soft_Serial package, which can use any GPIO pin as TX UART pin.
package Soft_Serial is
Serial_Pin : Boolean renames AVR.MCU.PORTB_Bits (2);
Serial_Pin_DD : Boolean renames AVR.MCU.DDRB_Bits (2);
procedure Write_Byte(B : Interfaces.Unsigned_8);
procedure Write (S : AVR.Strings.AVR_String);
The interesting bits in the implementation are:
MCU_FREQ : constant := 16_000_000;
procedure Wait_A_Little is new AVR.Wait.Generic_Wait_USecs
(Crystal_Hertz => MCU_FREQ,
Micro_Seconds => 102);
procedure Write_Byte(B : Interfaces.Unsigned_8) is
Data : Interfaces.Unsigned_8 := B;
Mask : Interfaces.Unsigned_8 := 1;
Serial_Pin := False;
for I in Interfaces.Unsigned_8 range 0 .. 7 loop
if (Data and Mask) = Mask then
Serial_Pin := True;
Serial_Pin := False;
Mask := Mask * 2;
Serial_Pin := True;
Basically, the Write_Byte procedure will put the GPIO pin up or down
with certain intervals.
The Wait_A_Little procedure has magic number 102, which gives us UART
speed 9600bps. (9600bps means one bit about every 104 microseconds,
the difference comes from the inaccurate internal oscillator.)
The procedure uses 8N1 format, meaning that the start bit (pin low)
is sent first, then the data byte as 8 bits, and finally one stop bit (pin high).
Open Gatekeeper settings located in System Preferences > Security & Privacy.
Set Allow applications downloaded from: to Anywhereand confirm by pressing Allow From Anywhere.
Run the application.
Once the application has been successfully launched, it no longer goes through Gatekeeper; so, restore Gatekeeper settings to the default option Mac App Store and identified developers after successfully launching the application.
EtherScope is a monitoring tool that analyzes the
Ethernet traffic. It runs on a STM32F746 board, reads the Ethernet packets, do some real-time
analysis and displays the results on the 480x272 touch panel. The application is completely
written in Ada 2012 with:
The GNAT ARM embedded runtimes is the Ada 2012 ravenscar runtime that provides support for interrupts, tasks, protected objects and other Ada features.
The EtherScope application which performs the analysis and displays the information.
The traffic analyzer inspects the received packet and tries to find interesting information about it.
The analyzer is able to recognize several protocols. New protocols may easily be added in the future.
The first version supports:
Analysis of Ethernet frame to identify the devices that are part of the network with their associated IP address and network utilization.
Analysis of IPv4 packet to identify the main IPv4 protocols including ICMP, IGMP, UDP and TCP.
Analysis of IGMP with discovery of subscribed multicast groups and monitoring of the associated UDP traffic.
Analysis of TCP with the identification of some well known protocols such as http, https, ssh and others.
Each analyser collects the information and is able to report the number of bytes, number of packets
and network bandwidth utilization. Some information is also collected in different graph tables so that
we can provide some visual graph about the network bandwidth usage.
Network setup to use EtherScope
To use EtherScope, you will connect the STM32F746 board to an Ethernet switch that you insert or have on your
network. By default, the switch will isolate the different ports (as opposite to a hub) and unicast traffic
is directed only to the concerned port. In other words, EtherScope will only see broadcast and multi-cast
traffic. In order to see the interesting traffic (TCP for example), you will need to configure the switch
to do port mirroring. By doing so, you tell the switch to mirror all the traffic of a selected port to the
mirror port. You will connect EtherScope to that mirror port and it will see all the mirrored traffic.
EtherScope in action
The following 4 minutes video shows the EtherScope in action.
EtherScope Internal Design
The EtherScope has several functional layers:
The display layer manages the user interaction through the touch panel. It displays the information that was analyzed and manages the refresh of the display with its graphs.
The packet analyzer inspects the traffic.
The Ethernet network driver configures the Ethernet receive ring, handles interrupts and manages the reception of packets (the transmission part is not used for this project).
The Ada Drivers Library provides a number of utility packages from their samples to manage the display and draw text as well as some geometric forms.
The GNAT ARM ravenscar runtime provides low level support for the STM32 board configuration, interrupt and task management. It also brings a number of important drivers to control the touch panel, the button, SPI, I2C and other hardware components.
The EtherScope.Receiver is the package that has the receiver task that loops to receive a
packet from the Ethernet driver and analyzer it through the analyzer. Because the result of
the analysis is shared between two tasks, it is protected by the DB protected object.
The EtherScope.Display provides several operations to display the analysis in various forms
depending on the user selection. Its operations are called repeatedly by the etherscope main
loop. The display operation fetch the analysis from the DB protected object and format the
result through the UI.Graphs or text presentations.
The Ada Embedded Network is a small IPv4 network stack
intended to run on STM32F746 or equivalent devices. This network stack
is implemented in Ada 2012 and its architecture has been inspired by
the BSD network architecture described in the book "TCP/IP Illustrated, Volume 2, The Implementation" by
Gary R. Wright and W. Richard Stevens.
This article discusses the Ethernet Driver design and implementation. The IP protocol layer part will
be explained in a next article.
In any network stack, the buffer management is key to obtain good performance. Let's see how it is modeled.
The Net.Buffers package provides support for network buffer management. A network buffer can hold a
single packet frame so that it is limited to 1500 bytes of payload with 14 or 16 bytes for the Ethernet header.
The network buffers are allocated by the Ethernet driver during the initialization to setup the
Ethernet receive queue. The allocation of network buffers for the transmission is under the responsibility
of the application.
Before receiving a packet, the application also has to allocate a network buffer. Upon successful reception
of a packet by the Receive procedure, the allocated network buffer will be given to the Ethernet
receive queue and the application will get back the received buffer. There is no memory copy.
The package defines two important types: Buffer_Type and Buffer_List. These two types are
limited types to forbid copies and force a strict design to applications. The Buffer_Type
describes the packet frame and it provides various operations to access the buffer. The Buffer_List defines a list of buffers.
The network buffers are kept within a single linked list managed by a protected object.
Because interrupt handlers can release a buffer, that protected object has the priority
System.Max_Interrupt_Priority. The protected operations are very basic and are in O(1) complexity so that their execution is bounded in time whatever the arguments.
Before anything, the network buffers have to be allocated. The application can do this
by reserving some memory region (using STM32.SDRAM.Reserve) and adding the region with
the Add_Region procedure. The region must be a multiple of NET_ALLOC_SIZE constant.
To allocate 32 buffers, you can do the following:
What happens if there is no available buffer? No exception is raised because the networks stack
is intended to be used in embedded systems where exceptions are not available. You have to
check if the allocation succeeded by using the Is_Null function:
if Packet.Is_Null then
null; -- Oops
The Net.Interfaces package represents the low level network driver that is capable of sending and
receiving packets. The package defines the Ifnet_Type abstract type which defines the three
Initialize to configure and setup the network interface,
Send to send a packet on the network.
Receive to wait for a packet and get it from the network.
STM32 Ethernet Driver
The STM32 Ethernet driver implements the three important operations required by the Ifnet_Type abstraction.
The Initialize procedure performs the STM32 Ethernet initialization, configures the receive and transmit
rings and setup to accept interrupts. This operation must be called prior to any other.
Sending a packet
The STM32 Ethernet driver has a transmit queue to manage the Ethernet hardware transmit
ring and send packets over the network. The transmit queue is a protected object so that
concurrent accesses between application task and the Ethernet interrupt are safe.
To transmit a packet, the driver adds the packet to the next available transmit descriptor.
The packet buffer ownership is transferred to the transmit ring so that there is no memory copy.
Once the packet is queued, the application has lost the buffer ownership. The buffer being
owned by the DMA, it will be released by the transmit interrupt, as soon as the packet is sent (3).
When the transmit queue is full, the application is blocked until a transmit descriptor becomes
Receiving a packet
The SMT32 Ethernet driver has a receive queue which is a second protected object, separate from
the transmit queue. The receive queue is used by the Ethernet hardware to control the Ethernet
receive ring and by the application to pick received packets. Each receive descriptor is assigned
a packet buffer that is owned by default to the DMA. When a packet is available and the application
calls the Wait_Packet operation, the packet buffer ownership is transferred to the application
to avoid any memory copy. To avoid having a ring descriptor loosing its buffer, the application gives
a new buffer that is used for the ring descriptor. This is why the application has first to
allocate the buffer (1), call the Receive operation (2) to get back the packet in a new
buffer and finally release the buffer when it has done with it (3).
Receive loop example
Below is an example of a task that loops to receive Ethernet packets and process them.
This is the main receiver task used by the EtherScope
The Ifnet driver initialization is done in the main EtherScope task. We must not use
the driver before it is full initialized. This is why the task starts to loop for the
Ifnet driver to be ready.
task body Controller is
use type Ada.Real_Time.Time;
Packet : Net.Buffers.Buffer_Type;
while not Ifnet.Is_Ready loop
delay until Ada.Real_Time.Clock + Ada.Real_Time.Seconds (1);
Then, we allocate a packet buffer and enter in the main loop to continuously
receive a packet and do some processing. The careful reader will note that there
is no buffer release. We don't need that because the Receive driver operation
will pick our buffer for its ring and it will give us a buffer that holds the received packet.
We will give him back that buffer at the next loop.
In this application, the number of buffers needed by the buffer pool is the size of the Ethernet Rx ring plus one.
One fascinating property of the LZMA data compression format is that it is actually a family of formats with three numeric parameters that can be set:
The “Literal context bits” (lc) sets the number of bits of the previous literal (a byte) that will be used to index the probability model. With 0 the previous literal is ignored, with 8 you have a full 256 x 256 Markov chain matrix, with probability of getting literal j when the previous one was i.
The “Literal position” (lp) will take into account the position of each literal in the uncompressed data, modulo 2lp. For instance lp=1 will be better fitted for 16 bit data.
The pb parameter has the same role in a more general context where repetitions occur.
For instance when (lc, lp, pb) = (8, 0, 0) you have a simple Markov model similar to the one used by the old "Reduce" format for Zip archives. Of course the encoding of this Markov-compressed data is much smarter with LZMA than with "Reduce". Additionally, you have a non-numeric parameter which is the choice of the LZ77 algorithm – the first stage of LZMA.
The stunning thing is how much the changes in these parameters lead to different compression quality. Let’s take a format difficult to compress as a binary data, losslessly: raw audio files (.wav), 16 bit PCM. By running Zip-Ada's lzma_enc with the -b (benchmark) parameter, all combinations will be tried – in total, 900 different combinations of parameters! The combination leading to the smallest .lzma archive is with many .wav files (but not all) the following: (0, 1, 0) – list at bottom . It means that the previous byte is useless for predicting the next one, and that the compression has an affinity with 16-bit alignment, which seems to make sense. The data seems pretty random, but the magic of LZMA manages to squeeze 15% off the raw data, without loss. The fortuitous repetitions are not helpful: the weakest LZ77 implementation gives the best result! Actually, pushing this logic further, I have implemented for this purpose a “0-level” LZ77  that doesn’t do any LZ compression. It gives the best output for most raw sound data. Amazing, isn’t it? It seems that repetitions are so rare that they output a very large code through the range encoder, while weakening slightly and temporarily the probability of outputting a literal - see the probability evolution curves in the second article, “LZMA compression - a few charts”. Graphically, the ordered compressed sizes look like this:
and the various parameters look like this:
The 900 parameter combinations
The best 100 combinations
Many thanks to Stephan Busch who is maintaining the only public data compression corpus, to my knowledge, with enough size and variety to be really meaningful for the “real life” usage of data compression. You find the benchmark @ http://www.squeezechart.com/ . Stephan is always keen to share his knowledge about compression methods. Previous articles:
____  Here is the directory in descending order (the original file is a2.wav). 37'960 a2.wav 37'739 w_844_l0.lzma 37'715 w_843_l0.lzma 37'702 w_842_l0.lzma 37'696 w_841_l0.lzma 37'693 w_840_l0.lzma 37'547 w_844_l2.lzma ... 32'733 w_020_l0.lzma 32'717 w_010_l1.lzma 32'717 w_010_l2.lzma 32'707 w_011_l1.lzma 32'707 w_011_l2.lzma 32'614 w_014_l0.lzma 32'590 w_013_l0.lzma 32'577 w_012_l0.lzma 32'570 w_011_l0.lzma 32'568 w_010_l0.lzma  In the package LZMA.Encoding you find the very sophisticated "Level 0" algorithm
if level = Level_0 then while More_bytes loop LZ77_emits_literal_byte(Read_byte); end loop; else My_LZ77; end if;
Here are some recent updates to our Free Tools and Libraries page:
September 30, 2016: Added X-Cleaner, a Windows tool to securely erase data.
August 11, 2016: Added PUGIXML Ada, a set of Ada bindings to PUGIXML, a lightweight XML processing library.
Added ZStd for Ada, Ada bindings to ZStandard, a new lossless compression algorithm.
July 19, 2016: Added Libsodium-ada, a set of thick Ada bindings to libsodium. Libsodium is a portable implementation of the NaCl encryption, hashing, and authentication library.
June 22, 2016: Added Container JSON, utilities for serializing/deserializing Ada containers to/from JSON.
Added SymExpr, a generic package for manipulating simple symbolic expressions.
May 19, 2016: Added AdaBase, a new database interface for Ada.
Added Imago, a binding to DevIL (a universal image handling library).
(This post will be periodically updated – Webmaster.)
Here are a few plots that I have set up while exploring the LZMA compression format.
You can pick and choose various LZ77 variants - for LZMA as well as for other LZ77-based formats like Deflate. Of course this choice can be extended to the compression formats themselves. There are two ways of dealing with this choice.
You compress your data with all variants and choose the smallest size - brute force, post-selection; this is what the ReZip recompression tool does
You have a criterion for selecting a variant before the compression, and hope it will be good enough - this is what Zip.Compress, method Preselection does (and the ZipAda tool with -eps)
If the computing resource - time, even energy costs (think of massive backups) - is somewhat limited, you'll be happy with the 2nd way. A criterion appearing obviously by playing with recompression is the uncompressed size (one of the things you know before trying to compress).
Obviously the BT4 (one of the LZ77 match finders in the LZMA SDK) variant is better on larger sizes than the IZ_10 (Info-Zip's match finder for their Deflate implementation), but is it always the case ? Difficult to say on this graphic. But, if you cumulate the differences, things begin to become interesting.
Funny, isn't it ? The criterion would be to choose IZ_10 for sizes smaller than the x-value where the green curve reaches its bottom, and BT4 for sizes larger than that x-value.
Another (hopefully) interesting chart is the way the probability model in LZMA (this time, it's the "MA" part explained last time) is adapted to new data. The increasing curves show the effect of a series of '0' on a certain probability value used for range encoding; the decreasing curves show the effect of a series of '1'. On the x-axis you have the number of steps.
This summer vacation's project was completed almost on schedule: write a LZMA encoder, whilst enjoying vacation - that is, work early in the morning and late in the evening when everybody else is sleeping; and have fun (bike, canoe, visiting caves and amazing dinosaurs fac-similes, enjoying special beers, ...) the rest of the day.
Well, "schedule" is a bit overstretched, because with a topic as tricky as data compression, it is difficult to tell when and even whether you will succeed...
LZMA is a compression format invented by Igor Pavlov, which combines a LZ77 compression and range encoding.
With LZ77, imagine you are copying a text, character by character, but want to take some shortcuts. You send either single characters, or a pair of numbers (distance, length) meaning "please copy 'length' characters, starting back 'distance' characters in the copied text, from the point where the cursor is right now". That's it! LZ77 is a well covered subject and is the first stage of most compression algorithms. Basically you can pick and choose an implementation, depending on the final compression size.
Range encoding is a fascinating way of compressing a message of any nature. Say you want to send a very large number N, but with less digits. It's possible - if some of the digits (0 to 9), appear more frequently, and some, less. The method is the following. You begin with a range, say [0, 999[. You subdivide it in ten intervals, corresponding to the digits 0 to 9, and calibrated depending on their probability of occurrence, p0 .. p9. The first digit of N is perhaps 3, and its corresponding interval is, say, [295, 405[. Then, you continue with the second digit by subdividing [295, 405[ in ten intervals. If the second digit is 0, you have perhaps now [295, 306[, representing the partial message "30". You see, of course, that if you want to stick with integers (with computers you don't have infinite precision anyway), you lose quickly precision when you set up the ten intervals with the probabilities p0 .. p9. The solution is to append from time to time a 0 to the interval, when the width is too small. So, if you decide to multiply everything by 10 each time the width is less than 100, then the interval for "30" will be now [2950, 3060[. Some n digits to be encoded later (after n subdivisions and some x10 when needed) your interval will perhaps look like [298056312, 298056701[. The bounds become larger and larger - second problem. Solution: you see that the leftmost digits won't change anymore. You can get rid of them and send them as a chunk of the compressed message. The compression will be better when symbols are much more frequent than others: the closer the probability is to 1, the more the range width will be preserved. If the probability was exacly 1, the width wouldn't change at all and this trivial message with only the same symbol wouln't take any space in its compressed form! It is an absurd case, but it shows why compression methods such as LZMA are extremely good for very redundant data. That's how the basic range encoding works. Then, a funny thing is that you can encode a mix of different alphabets (say digits '0' to '9' and letters 'A' to 'Z') or even the same alphabet, but with different probabilities depending on the context, provided the decoder knows what to use when. That's all for range encoding (you find a more detailed description in the original article ).
LZMA's range encoder works exclusively on a single, binary alphabet (0's and 1's), so the range is always divided in two parts. But it works with lots of contextual probabilities. With some parameters you can have millions of different probabilities in the model! The probabilities are not known in advance, so in this respect LZMA is a purely adaptive compression method: the encoder and the decoder adapt the probabilities as the symbols are sent and received. After each bit encoded, sent, received, decoded, the entire probability set is (and has to be) exactly in the same state by the encoder and by the decoder.
Developing an encoder from scratch, even if you have open-source code to reproduce, is fun, but debugging it is a pain. A bug feels like when something doesn't work in a PhD work in maths. No way to get help from anybody or by browsing the Web. By nature, the compressed data will not contain any redundancy that would help you fixing bugs. The decoder is confused on faulty compressed data and cannot say why. For range encoding, it is worse: as in the example, digits sent have nothing to do with the message to be encoded. The interval subdivision, the shipping of the leading interval digits, and the appending of trailing '0', occur in a way which is completely asynchronous. So, the good tactic is, as elsewhere, to simplify and divide the issues to the simplest. First, manage to encode an empty message (wow!). It seems trivial, but the range encoder works like a pipeline; you need to initialize it and flush it correctly. Then, an empty message and the end-of-stream marker. And so on. Another source of help for LZMA is the probability set: it needs to be identical at every point as said before.
The results of this effort in a few numbers:
LZMA.Encoding, started July 28th, first working version August 16th (revision 457).
Less than 450 lines - including lots of comments and some debugging code to be removed!
5 bugs had to be fixed.
To my (of course biased) opinion, this is the first LZMA encoder that a normal human can understand by reading the source code.
Zip-Ada's Zip.Compress makes use of LZMA encoding since revision 459.
The source code is available here (main SourceForge SVN repository) or here (GitHub mirror).
Back to vacation topic (which is what you do often when you're back from vacation): a tourist info sign was just perfect for a 32x32 pixels "info" icon for the AZip archive manager.
Click to enlarge
The beautiful sign
By the way, some other things are beautiful in this town (St-Ursanne at the Doubs river)...
 G. N. N. Martin, Range encoding: an algorithm for removing redundancy
from a digitized message, Video & Data Recording Conference,