any suggestions on buffer compression in firmware?

hi,

I'm working on a protocol to compress the buffer space on arduino, i do not know how far i could get, or what the merits are other than to compress short movements. the goal in the text below is to explain it and where i am coming from.

basically it takes a lot less effort to have arduino with a large buffer, that can fill up completely with long line segments and buffer thru complex short moves to not pause or slow down drastically. this buffer would decompress and send data as the normal buffer would, and receive data as the normal buffer would. it would be a lot more complex in how it stored data though..


this is in part to [forums.reprap.org]
feel free to comment there on protocol standards for firmware and codecs.

One of the goals is to increase the buffer size dramatically for short moves while maintaining a neutral stand on firmware. meaning it is more about method, then specifics for firmware code.

I am at the point of searching for a method to greatly increase the internal buffer of arduino particularly around angles and corners. For now this method will compress data after it is confirmed by check-sum and before it goes into buffer, and it will decompress data after it is called from buffer by programming firmware.

The overhead for buffering is currently quite large, and the reasoning for the buffer is to prevent long pauses during serial transmitting / receiving. the buffer size is 4 gcode lines.

the method proposed is based on this thinking.

Small movements means large buffering as moves complete quickly and buffer drains quicker
Large movements such as long lines can fill buffer faster than it drains.
The buffer is beneficial to be large enough for small moves to not drain completely and pause/ slowdown printer.



The thoughts so far on this are as follows.
data size is variable storage size of data, meaning optimized to be small for small moves. Also scaling the smallest movement down to the resolution detail in calculations of my last read into firmware was 0.1mm resolution. anything smaller than that is ignored.

There are many objects that have complex shapes to them, that do not need the entire coordinate system stored for compression. Currently arduino memory errors are not an issue. Since the data is compressed as it goes into the buffer, it has already been checksum confirmed so serial data has been verified.

The thoughts on this compressed buffer are as follows

compressing data down to this MNXXMNYY and 00000000 (special command to follow)
n is negative or posative.
M is multiplier mode M=0 means multiply by 1 M=1 means multiply by 32 xx and yy are the data of each line by 0.1mm x multiplier.

10001000 is complete data stored


00000000 since x and y are not moving this would otherwise be doing nothing, this is command for special instruction mode the next byte in this mode is MNBBBBBB M=0 it is z in .1mm M=1 it is E in +/- 63 values N is postage or negative


when storing in buffer, look at current position data as normal, look at what position the buffer is at and add to it or subtract from it. to match current values after buffered move is complete. commands that zero out positioning will wait to run until buffer is empty . the buffer reference at half values for x and y

when a move is large you break it down to several moves in the buffer still less than 12bytes, when moves are small they take 1 to 4 bytes. moves are added up and then the last byte 10001000 sends int out of buffer as uncompressed data to go into the gcode parser.

the idea is to have at least 60 short moves buffered by the time a 10mm segment line is completed, giving the arch angle, or circle the buffer data needed to complete movement without waiting for more info from pc.

a 1000 1000 means movement data complete for this segment. (so 10001000, should be avoided otherwise, and it would be avoided because it does not move x or y )

this is just the buffer part of reprap code i am talking about here. There is still need to make data sent efficiently, however after looking at it closer most parts made by reprap are long lines with a few corners and circles.


data below will be edited later, and possibly include diagram information:

The average movement per line segment on corners and angles is between .1mm to 2mm in size. at 60mm/s and at 57600baud, that is 57600/10 =5760 bytes/20 char per line=288cmds a second max /60mm/s=max efficiency .2mm with buffer not emptying out.
data rate is1/288 per second or 0.00378 seconds
data delay rate error free is 0.004 seconds for round trip checksum
0.00778seconds per command if 20char per line
1/.00778~128 commands a second
which would make the data buffer in practice start to empty out at any distances less than .5mm at 60mm/s error free.
fat chance and good luck at anything should you have a data error. buffer will become clear
. big deal you say?

take a circle with a diameter of 4mm make it 30 lines of code 4*pie/30=.41 buffer will empty out. this is extreme, but often what happens in part corners. yes you could modify your polygons and do octagons instead of circles, and you could chance that every angle and corner of your print job is over .41mm in size or 1mm is size at 24mm/s

if there ever is an error in check-sum around a small movement, your buffer will empty, and if the small move is followed by another small move it will empty.

solution: increase buffer size to large size. how. compress small moves,compress large moves in buffer.

if buffer is full it will wait a little bit before sending last acknowledge.

subject to edits and changes.

any thoughts, comments, what works what does not? thanks!

Edited 3 time(s). Last edit at 06/08/2011 07:20PM by jamesdanielv.

just looked at the latest tonokip firmware [www.thingiverse.com] to try buffer compression in as it is really easy to follow where the code goes. It would be a good test into how buffering data in advance would help, not that i have any firmware preferences.

It seems it is buffering 256char for a total of 8 buffers. yikes. I did calculations based on what resolution the printer has, and there is buffer optimizations even before i do compression techniques. i also wonder why it is only using 1k to buffer.

if the incoming data is to be buffered it can be trimmed down quite a ways as anything less than .1mm is pointless. so a buffer really only needs to be 32 bytes for tonokip as long as numbers are truncated. allowing for if 2048bytes are free to have a buffer of 64 which is enough for me to test the buffer strategy on circles and angles.

each axis just needs 6 char (space)(X/y/z/e/f )NNN.N and inches could be nn.nn

and then a 2 char G1 or G0 in front. any mcode command is less than 10 characters.
this allows for .1mm resolution

I'll test this out in a little while the 1280 mega . it sounds so good I'm sure something is missing here...

anther thing. atmel data sheets state ATmega1280 has 8k of sram why not increase buffer to use 4k?

I guess I'll know more when i look at the code in how the tonokip firmware buffer stores information.

I'm a little rusty on efficiently trimming char but the trim will happen after the serial data is read.

no time line yet. Sure there will be a brick wall in this...

Edited 1 time(s). Last edit at 06/06/2011 06:23AM by jamesdanielv.

jamesdanielv Wrote:
-------------------------------------------------------
> anther thing. atmel data sheets state ATmega1280
> has 8k of sram why not increase buffer to use 4k?

You have to be careful of the stack. On atmegas, it starts at the end of RAM and builds backwards towards the start. There is NO provision for detecting if it's encroached on variable space (which builds up from the start of ram) and if it does, crashes and data corruption are absolutely certain. All variables that are not global are allocated on the stack when the code block that contains them is entered. Every function call pushes a subset of the 32 registers (possibly all of them) onto the stack so it gets used fairly heavily unless programs are carefully written to keep its use to a minimum.

I'm not sure about the internal structure of tonokip, but teacup gets far more advantage from increasing the movebuffer than the serial buffer. This allows precalculation of moves for small fast sections during slower sections.

Also, serial bandwidth is not our bottleneck for the vast majority of prints. At 115200 baud, we can send 11k per second. If each gcode line is 32 bytes, and our speed is 100mm/second, our minimum move length is just 0.3mm. That's assuming no acceleration (which slows down sequences of small moves).

---

-----------------------------------------------
Wooden Mendel
Teacup Firmware

thanks. so basically there is minimal benefit as long as your not doing check-sum right?

jamesdanielv Wrote:
-------------------------------------------------------
> thanks. so basically there is minimal benefit as
> long as your not doing check-sum right?

why would checksumming make any significant difference?

---

-----------------------------------------------
Wooden Mendel
Teacup Firmware

Quote

why would checksumming make any significant difference?

Because of the delay in receive and send data of the serial to USB ftdi controller.

The USB device driver driven by the host machine updates every 2ms. If firmware acknowledges the data as good it still takes 2ms for host to know about it and it takes 2ms more for the host data it is sending the controller to get to the ftdi chip buffer.

At some point it does not matter how fast communication is if it is 2 ways the biggest delay is the host driver. The most effective way to deal with this is to buffer the moves during long line segments, where several lines of serial data are processed and checksum returned.


Also you could just incorporate Forward error correction in the data, but that is in a different topic here: [forums.reprap.org]

I think the teacup firmware handles data verification differently.

Quote

why not increase buffer to use 4k?

Well, do that. Increase MOVEBUFFER_SIZE in config.h to 16, 32, 64, ...

Quote

The USB device driver driven by the host machine updates every 2ms.

Does it really work that way? Booooh!

That nicely explains why waiting for an "ok" before sending the next line significantly slows down communications. To something like 2 or 3 lines per second. I'm working on a trusty Mac, Mac OS X 10.4.10.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

increased buffer size. now working on condensing gcode to fit in smaller space. then will work on buffer compression. ran into a few unexpected things like adc conversion crashes arduino if it is ad sampling and storing in buffer and reading serial.... taken care of now... changed how adc works.

also ran into a sprinter firmware bug where e axis seemed to be doign a div by zero in the e_steps code.

now will try to condense buffer to take 10 bytes for each line.

Edited 1 time(s). Last edit at 06/14/2011 06:53PM by jamesdanielv.