Implementing Postscript as firmware

Quote
RepRap Software for RepRap Hardware aka47 Wrote:
> Julie
>
> The suggestion here certainly is not that everyone
> must develop the firmware.

My impression, was that these threads were for those of us who are actively working on the firmware. Ways of improving the system to make it practical for anyone to use,

The sort of open ended discussion, about what could be done is good. However some grounding in reality must be understood in order to change.

The idea of host printing or nothing is a good place to start discussing a stand alone system. As a practical example, I will use the development of a simple postcript printer. This can be then expanded into the changes needed to make this model work with a 3d printer.

In the real world of postscript printers these are a complicated system. First there is the core. This in effect is ghostscript. One talks to ghostscript through a unix pipe. This is simply an abstraction of the data stream as an interpreter. The input pipe only responds to parseable commands. The output pipe(s) are in effect a turning engine, it can return any form of data abstraction.

These data abstractions are the heart of the system. The language parser which is stacked based consists of a database management system, and a vector drawing engine. The database management system is recursive and provides for the ordering of text, numerical or graphical data.

Note, that the core of the postcript abstraction does not contain any knowledge of image rasters, file systems, or network protocols. A bitmap image is part of the database management system and is nothing more than an array of vectors. Images are returned from the parser to the output pipe in the form of an array.

Note that I have mentioned nothing of fonts or text processing. These are inherently defined inside the parser as recursive data groups stored inside the database. The color raster engine is also a subset of the database management process.

To implement a printer using these abstractions, one first needs a network model in order to attach devices to the input pipe. This could be a simple as an Rs232 connector, or parallel port. Most end users now expect a fully socketed system, such as TCP/IP.


It was quickly found that non roman font sub programs took a lot of space, so some printers made advantage of an internal hard disk to store database information onto. Again, the connection to these drives is through the equivalent of a unix pipe.

It can be seen that an operating system inside the printer is needed. This would present the need for a processor at least as powerful as an ARM7. The vector nature of the fundamental data type, implies for hardware multiplication of either fixed or floating point numbers.

It can also be seen that in the case of a postscript printer, that the host and the printer are a self contained unit.

How does this then affect the change to reality that reprap would need?

First there is the operating system. My guess from reading these forums for a year, is the current choice by 99% of the participants is some form of unix. 97% probaby prefer Linux. One percent may use BSD (including Mac OSX) and the remaining two percent are dependent on ports to the windows command line structure.

Due to the 8 bit nature of the Arduino family of controllers, there is only one pipe from the OS to the firmware. This usually take the form of a serial back channel, often implemented with a USB protocol.

The internal interpreter on the arduino is pretty much limited to simple protocols like G-code. No OS or scheduler is used.

It has been argued that this simple G-code interpreter could be replaced with something like fourth. This would allow for parser to become recursive, like postscript. Any protocol sub parsers could be downloaded and processed. This may remain a valid subject for discussion, however I would suggest a separate thread be created.

Would it be possible to implement the postscript abstraction on the existing Arduino hardware? Could the existing hardware support a subset of the Ghostscript/postscript kernal?


Vectors inside postscript are stored as cubic splines. This makes drawing arbitrary curves possible. Each vector contains 6 points. These are start, end and 4 control point that warp the curve away from the start and end points. This should be possible to implement inside the AVR processor using 16bit fixed point scaled numbers

Since separate motor controllers are used, these splines could be calculated by the motor processors directly. The motor control process would only need to caluclate the parts of the curve needed at it's own resolution.


Postscript uses a key/value dictionary similar to XML to handle database extractions. These are built and extended by simple stack manipulation operators.

I have written multi-threaded MIDI applications using the mega88. Implementing sync in,FAT-32 SD/MM support, and the necessary musical note In/Out events. The AVR assembly instruction set are C primitives. This makes it easy to define indexed stack frames with 64 levels of offset. I have a microschedular with semaphore message system which in implemented in a handful of bytes and a timer interupt.

So already there is enough work done to implement a micro postscript kernal on the AVR.

Since a 3D printer is already vector based, the complex raster engine would not be needed. This does away with much of the matrix multiplications used to build the enormous raster buffers. Some scaling process would be needed, this could be handled by a separate motor control processor. The mega88 supports hardware multiply, so some fixed/floating point conversion could also be handled.

Extending postscript into 3D might be an issue. In theory the image is defined by opaque layers of paint. The simplest would be to define each "page" as a slice through the object. Internal to postscript are the rules for even/or fill, so it would be possible to define the "fill pattern" inside the controller. Solid 3D could be represented by fill color, where the saturation (grayscale) is the height of the filled area and the two color vectors represent which head is used to apply the material. This may be too much for the existing hardware, but could be implemented with a 32 bit processor such as ARM7.

Since the internal processes inside postscript can be defined with pipes, multiple processors can be used. To deepen the stacks, it is possible to connect an IDE hard drive to even some of the oldest AVR processors, which have large pin counts.

Implementing a postscript microkernal may be an area I personally will look into.

This will not address the issue of self replication, although postscript is recursive (until one runs out of stack space)

A postscript microkernal, would make it easy to connect any ASCII terminal to the input pipe. The return pipe can dump the stack back to the user.

Hardware states can be returned through the normal postscript internal dictionaries such as statusdict.

Font sets could be stored on SD/MMC cards Any existing postscript font could be accessed. This might require a separate "font engine" processor.

Design software would still be needed, at least to slice the object into "pages"


In summery, then it should be possible to use the existing hardware to develop a simple to use interpreter along the postscript model. This would be a long term development project. A number of issues remain, which will need further investigation.


-julie

Cool.

So who is going to start doing the work?

Stephen

It sounds do-able, go for it.

You may want to consider using the Arduino Mega it gives you a whole bunch more and looks like a reasonable bet for the next step in controller evolution....

aka47

---

Necessity hopefully becomes the absentee parent of successfully invented children.

My time is probably better spent, getting a repstrap working using my old CNC as a base. Eventually I want to move the controller away from windows and onto a form of the reprap driver system. Probably re-working the Arduino code into stand alone AVR code, as I am more familiar with that toolchain and development environment.

I did take a look at the "red book" (postscript bible.) The question is could one implement a subset, or would something "Ghostscript" compatable be expected to handle any object of the language including the HPGL support and PDF generation.

Years ago, I wrote a simple interpreter for reading Adobe illustrator documents, these use a set of standard definitions, like a library that read a compressed version of the paths.

In the software for hardware thread, there was some more discussion regarding the validity of the postscript model.

Adobe, put the language in public domain, they did retain the trademark to the name "PostScript", which is why the open source implementation is called Ghostscript.

This is probably why, few low cost printers embed Postscript, to save licensing fees. Especially when Ghostscript is out there and can build a page on the host.

It may be that in the long run, a reprap type device could use a turing complete interpreter, Especially if others do evolve into the arduino Mega.

-julie

snip

Edited 4 time(s). Last edit at 08/18/2011 12:57PM by ElectricMucus.

Also the idea of task manager on the arduino is more real than you would think. The current firmware pauses when buffering data, and during moves when it collects serial data. What becomes frustrating is how much of the time current code does nothing but loop to kill time.....

It is difficult to code to do more than one task at a time.
Do loop until this time
vs
Is it time yet to do?

void loop
do task
delay(timer)
void loop
{
do task1;
delay1(timer);
void loop;
do task2;
delay2(timer);
do task3;
delay3(timer);

}
or


void loop
{
if (timer==delay1) {do task1;}
if (timer==delay2) {do task2;}
if (timer==delay3) {do task3;}

//time to spare in delays
do task4;

}


second way is much more efficient in programming and allows task 4 to start being processed in between the delays. it involves a known such as timer, and it is a simple form of a task manager... could user the millis() for the timer.

For parallel tasks on an ATmega, you use timers. Timers can be set to any delay (within some resolution) and they'll fire an interrupt when this delay has passed. Teacup firmware makes extensive use of such timers, the main loop just interprets the incoming G-code.

---

Generation 7 Electronics	Teacup Firmware	RepRap DIY

Traumflug; yes, but let me revise it slightly.

For parallel tasks on an ATmega you use a task manager. the task manager makes use of timers.

timers by themselves are not that good at handling multitasking. even when assigned to interrupts.

I think what traumflug is trying to say is that 3d printing only really has one high priority task, and that's firing out step pulses. It can be made to run quite quickly and therefore is a prime candidate to be stuffed into a timer interrupt.

All the other tasks can run in sequence from main loop, and they'll sort stuff out between them quite happily. Reading serial and interpreting gcode can be merged into one workflow, and checking temperature sensors and managing heaters happens regularly but isn't time critical (unless you're leaning on your PID's D term to be really useful) so it can go in the main loop too and just check a flag set by a timer every so often.

If you're generating steps from a busy loop, task management becomes a lot more complex from that one change alone.

---

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

Seems like this thread came back from the dead.

I started to implement some of this a few years back in assembly. The Teacup solution seemed to have more support so I have not done much. Still need to order threaded rod and machine the supports, but that is another subject.

Most of my projects use a small microkernal. This is necessary when working with MIDI. To implement a simple task handler I use counting semaphores. The tricky part is dealing with memory and stack allocations. I modeled things after some 8051 examples. I use a fixed sized stack for each task. I also save most registers on task switch.

Counting semaphores are simple to implement. Set an interrupt timer to a fixed period like 1 ms. All the interrupt does is increment a location in memory. (spare registers can be used if memory is tight) Each task is assigned a byte of memory (or two depending on how long the delays are) If the counter is all 1s or -1 then the semaphore is not counting. Anything else the semaphore is decremented during the interrupt. I usually dedicate 1 direct access register to the task flags. When the count reaches zero, the flag is set. The stack pointer set to the handler for that task and calls said handler. That is all the interrupt does.

To switch tasks I use the function _wait(time) this function saves the return address and the registers onto the stack. It then polls on the semaphore.

One could get fancy with the scheduler and priorities. Usually with MIDI there is a lot of waiting so that the read routines that fill buffers fill until full. In these cases the count is not milliseconds, but is a watermark indicating how many bytes are in the buffer. Another task is timer based and reads the buffer outputting MIDI on the serial line when needed. A separate task polls the panel buttons or IR line for commands, like stop, play and file selections. I think this is called cooperative multitasking.

All this fits into a mega8515 as I use external ram to buffer the data.

I am not quite sure how to do this in C. Mostly because of the memory pool allocations and register mapping. My recent work with petite fat, was dependent on optimization settings. The best results came from a make file. The code so optimized it would not trace correctly in the debugger.

The flip side, was without optimization, too much garbage was being pushed onto the stack.

I am not too comfortable with how C handles interrupts. Usually I like to keep interrupts short. Set a flag or decrement a counter. For really tight assembly, such as reading a serial line, I sometimes dedicate the X register to the ring buffer. This means X can not be used by other functions, since the interrupt can happen at any time.

I also tend to avoid LDS and STS instructions, these take twice as much memory space. The index modes are much more efficient. Makes it easy in assembly to keep track of data as structures.

Should I revisit, some of this code, once I understand the line drawing acceleration better. I would probably assign the fast axis to counter. This would be updated in the timer. Each tick would then determine the slow count when needed.

I noted a few years back, the old NC systems, used counting registers, although they did not handle acceleration. Mostly just step and repeat to move the axis.

There is no real reason this has to be overcomplicated.

-julie

I've also written multitasking microkernels in c and assembly, albeit not for avr platform. In c, the best way to task switch is by firing a software interrupt of some kind, then all the registers are saved into the stack for you and you just have to alter the stack pointer before reti.

It really is overkill for our current workload, especially the ram needed for separate stacks. Add a few more tasks that don't condense well to short run functions and it may become more attractive

---

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

Ok, I think the point I was making was not clear. It is more effective to task without using delays. The only way to manage pauses effectively is with a task manager.


Void loop
{
if (timer==delay1) {do task1;}
if (timer==delay2) {do task2;}
if (timer==delay3) {do task3;}

//time to spare in delays
do task4;

}

Would make more sense if the tasks being completed were more complex



Void loop
{
if (timer==delay1) {do task1;}
if (timer==delay2) {do task2;}
if (timer==delay3) { switch(command_in_task3)
case 1
do task3instruction1
break;

case 2
do task3instruction2;}
break;

case 3
do task3instruction3;}
break;

case 4
do task3instruction4;
break;
command_in_task3++; }

//time to spare in delays

if (timer==delay4) { switch(command_in_task4)
case 1
do task4instruction1
break;

case 2
do task4instruction2;}
break;

case 3
do task4instruction3;}
break;

case 4
do task4instruction4;
break;
command_in_task4++; }
case 4
command_in_task4= 0 ;// resets for another loop
break;
}


This allows very complex instructions to run in true parallel.
Also using switch allows for very tight execution as loops are not that deep, switch performs in this case a simple progcounter+register jump.


as for speed of execution, this also runs faster than if it is all inside an interupt. it is a different method of programming.


if you normally program for a loop for moving motors, you process steps like this
*simplified, not actual code
loop(){
do_x_step()
do_y_step()
do_z_step()
do_e_step()
wait_millis_time_code_and_more
}

do_x_step()
{ x_pin_high
delay_1us //time to allows signal to be detected by ttl
x_pin_low}

do_y_step()
{ y_pin_high
delay_1us //time to allows signal to be detected by ttl
y_pin_low}

do_z_step()
{ z_pin_high
delay_1us //time to allows signal to be detected by ttl
z_pin_low}

do_e_step()
{ e_pin_high
delay_1us //time to allows signal to be detected by ttl
e_pin_low}

above code works, but it treats delays as well delays.

This is the alternative method this just uses simple codes, complex codes would use switch (simple codes may as well..)

if (step_x=timerx){xpin_high}

if (step_y=timery){ypin_high}

if (step_z=timerz){zpin_high}

if (step_e=timere){epin_high}

if (alldone_add_delay =timer_all_done){xpin_low; ypin_low; zpin_low;epin_low}


This method allows the proper delay time for ttl, but it does not do it per pin, and it does not use delay. It is timer based. And it frees up more time for complex tasks such as char processing of buffer and smoothing of line segments. Not between line segments, but during the line segment processing.

Using interrupts do allows several tasks at a time, but the delay loop still go wasted.

EDIT: This also would help in making an efficient post scripter? nice try by me. new topic needed.

anyway timers are considered events, and I'll post something that is a bare bones task manger that should handle >200khz on priority tasks

Edited 2 time(s). Last edit at 06/30/2011 12:21AM by jamesdanielv.

That is nice and all but what does this has to do with a hypothetical "postscript in 3d"?

From my pov this would be something like having a openscad interpreter in the firmware. Postscript can do much more than lets say gcode so unless you are some sort of realtime scheduler programming wizard you'd have a hard time getting that to run in an atmega.

yeah, some of the above comments went a little off topic. Atmega is a strong driving force, and you will be hard pressed to get people to stray away from the platform. It is not just the speed people are looking at, it is the quality of the ide, and the support network around it. ARM processors are far Superior, but currently if anyone comes out with arm, or pic based solutions, they will own every aspect of deploying it, including education customers, creating support networks, and documentation.

jamesdanielv Wrote:
-------------------------------------------------------
> yeah, some of the above comments went a little off
> topic. Atmega is a strong driving force, and you
> will be hard pressed to get people to stray away
> from the platform. It is not just the speed people
> are looking at, it is the quality of the ide, and
> the support network around it. ARM processors are
> far Superior, but currently if anyone comes out
> with arm, or pic based solutions, they will own
> every aspect of deploying it, including education
> customers, creating support networks, and
> documentation.

I think, at some point we will be best of adapting firmware to be multiplattform.
Not just that ARM is like the new Intel from a microcontroller POV, it's everywhere, it's fast and does cost the same as out 8bit controllers.
There are also other architectures which could be very helpful.

Especially in Robotics there is the Parallax Propeller chip which provides the best performance for our needs, is available and also has a large community behind it.
I'm not saying that we should stop supporting Atmel chips, just extending support to other platforms.

what is being said is that whoever does support them short term will go broke. there is no foundation to build upon the platform.

if you can make a good enough case raise funds thru one of those donation project sights.build, document, support and create a support group and improve ARMs foundation in the community.

Edited 2 time(s). Last edit at 07/07/2011 03:56PM by jamesdanielv.