Hi Timothy,
On Sat, 2005-08-20 at 14:24 -0400, Timothy Miller wrote:
> > Anyway, just thought I'd check in and let you know what's up. I've got a
> > pretty good model going for the flash interface and I wanted to check some
> > of
> > my assumptions before going any further. The IOs look like this:
Sorry for butting in late here, but I have been busy with other things
(SIGGRAPH amongst other things). I have attached two pieces of C code.
One compresses a file using a simple method (a sort of dumb LZ-ish thing
I made up, but I am sure is nothing new). I specifically wrote it for
compressing FPGA images, and it gets anything from 3:1 to 11:1
compression on Virtex-4 images, depending on gate density. I ended up
using it for ARM and TI DSP object code too, where it gets about 2.5:1
compression. Maximum compression on a repeated string is 128:1. It is
trivially modifiable to detect the end of a stream, so you don't need
length fields.
Decompression is _very_ simple, and requires a 256-byte buffer (you can
decrease that if you want to, at the expense of losing some compression
on long strings). It should be a breeze to implement in hardware if
required.
I thought this could help the OGP project in two ways:
1) It could be used to speed up FPGA boot, because you can read less
data from a slow flash, and decompress it in the Lattice chip before
writing it to the FPGA - you can run the sync serial interface to the
FPGA awfully fast.
2) It could be used to save space in the flash, allowing more images, or
BIOS images, or whatever.
When loading CPU code, I have generally just written an assembler
decompression stub that you simply concatenate onto the beginning of the
image. This meant I could do CPU boots using a tiny CPLD and a ROM (when
a CPU couldn't just read an image itself).
Feel free to use or not use this as you please. I figured it was easier
to just give you the code than ask if you wanted it. :-)
Keep well,
Ray
/* Crunch.c by Ray Heasman, Copyright (c) 2002 */
/* Released for the OGP project under the GPL */
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#define BUFLEN 256
#define MAXMATCH 256
int inPtr;
int outPtr;
int lastFlagPtr;
int smbCnt;
unsigned char outFlag = 0;
unsigned char *data;
unsigned char buffer[20*1024*1024];
int wfd;
void addFlag(int flag)
{
outFlag = (outFlag << 1) | flag;
smbCnt++;
}
void emitFlag(void)
{
buffer[lastFlagPtr] = outFlag;
lastFlagPtr = outPtr;
outPtr++;
outFlag = 0;
// printf("F");
}
void cleanUpFlags(void)
{
if (lastFlagPtr < outPtr) {
while (smbCnt < 8) {
addFlag(0);
}
buffer[lastFlagPtr] = outFlag;
}
}
void emitliteral(unsigned char value)
{
if (smbCnt == 8)
{
emitFlag();
smbCnt = 0;
}
buffer[outPtr++] = value;
addFlag(0);
// printf("L");
}
void emitcompressed(unsigned char value1, unsigned char value2)
{
if (smbCnt == 8)
{
emitFlag();
smbCnt = 0;
}
buffer[outPtr++] = value1;
buffer[outPtr++] = value2;
addFlag(1);
// printf("C");
}
int mlen(int hip,
int ip,
unsigned char *ibuf,
int size
)
{
int len;
len = 0;
while ((ip < size) && (ibuf[hip] == ibuf[ip]) && (len<MAXMATCH))
{
hip++;
ip++;
len++;
}
return(len);
}
int findMatch(int hip,
int ip,
unsigned char *ibuf,
int size,
int *offset)
// Find longest run of characters common to a range in the buffers
// Exhaustively searches
{
int bestLen, bestOff, currLen;
bestLen = bestOff = 0;
if (hip < 0)
{
hip = 0;
}
while (hip<ip)
{
currLen = mlen(hip, ip, ibuf, size);
if (currLen > bestLen)
{
bestLen = currLen;
bestOff = ip - hip;
}
hip++;
};
*offset = bestOff;
return bestLen;
}
void compressAndWrite(unsigned char *indata, int size)
{
int matchLen;
int offset;
int v1,v2;
inPtr = 0;
outPtr = 1;
smbCnt = 0;
lastFlagPtr = 0;
while (inPtr < size)
{
// Look for a match in the input buffer with its history
matchLen = findMatch(inPtr-BUFLEN, inPtr, indata, size, &offset);
// if ((matchLen>2) && (offset >= 250)) printf("Byte: %d Offset: %d Len: %d\n",inPtr, offset, matchLen);
// If we find a match long enough to bother with
if (matchLen > 2)
{
emitcompressed(offset-1, matchLen-1);
inPtr = inPtr + matchLen;
} else
{
emitliteral(indata[inPtr]);
inPtr++;
}
}
cleanUpFlags();
write(wfd, &(buffer[0]),outPtr);
printf("In len: %d, Out len: %d\n", inPtr, outPtr);
}
int main(int argc, char *argv[])
{
int fd;
struct stat fileInfo;
if (argc != 3)
{
printf("usage: %s infile outfile\n",argv[0]);
return(1);
}
fd = open(argv[1], O_RDONLY);
if (fd == -1) {
printf("Could not open file %s.\n",argv[1]);
return(1);
}
wfd = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR);
if (wfd == -1) {
printf("Could not open file %s.\n",argv[2]);
return(1);
}
printf("Writing to %s\n",argv[2]);
fstat(fd, &fileInfo);
data = mmap(0, fileInfo.st_size, PROT_READ, MAP_SHARED, fd, 0);
if (data == -1) {
printf("Could not mmap file.\n");
return(2);
}
compressAndWrite(data, fileInfo.st_size);
munmap(data, fileInfo.st_size);
close(fd);
close(wfd);
return(0);
}
/* Decrunch.c by Ray Heasman, Copyright (c) 2002 */
/* Released for the OGP project under the GPL */
#include <unistd.h>
#include <sys/types.h>
#include <sys/mman.h>
#include <sys/stat.h>
#include <fcntl.h>
#define BUFLEN 256
int inPtr;
int bufPtr;
int smbCnt;
unsigned char *data;
unsigned char buffer[BUFLEN];
int wfd;
void emitLiteral(unsigned char datum)
{
write(wfd, &datum, 1);
buffer[bufPtr] = datum;
bufPtr = (bufPtr + 1) % BUFLEN;
}
void emitMatch(int offset, int len)
{
int i,startPtr;
unsigned char datum;
startPtr = (BUFLEN+bufPtr-offset) % BUFLEN;
// printf("Emit match: S: %d L: %d\n",startPtr,len);
for (i=0;i<len;i++)
{
datum = buffer[startPtr];
startPtr = (startPtr+1) % BUFLEN;
emitLiteral(datum);
}
}
void decompressAndWrite(unsigned char *ibuf,
int size)
{
unsigned char flag;
inPtr = 0;
smbCnt = 8;
bufPtr = 0;
while (inPtr < size)
{
if (smbCnt == 8) {
flag = ibuf[inPtr++];
smbCnt = 0;
}
if (flag & 0x80) {
emitMatch(ibuf[inPtr]+1,ibuf[inPtr+1]+1);
inPtr += 2;
} else {
emitLiteral(ibuf[inPtr]);
inPtr++;
}
flag <<= 1;
smbCnt++;
}
}
int main(int argc, char *argv[])
{
int fd;
struct stat fileInfo;
if (argc != 3)
{
printf("usage: %s infile outfile\n",argv[0]);
return(1);
}
fd = open(argv[1], O_RDONLY);
if (fd == -1) {
printf("Could not open file %s.\n",argv[1]);
return(1);
}
wfd = open(argv[2], O_WRONLY | O_CREAT | O_TRUNC, S_IRUSR | S_IWUSR);
if (wfd == -1) {
printf("Could not open file %s.\n",argv[2]);
return(1);
}
printf("Writing to %s\n",argv[2]);
fstat(fd, &fileInfo);
data = mmap(0, fileInfo.st_size, PROT_READ, MAP_SHARED, fd, 0);
if (data == -1) {
printf("Could not mmap file.\n");
return(2);
}
decompressAndWrite(data, fileInfo.st_size);
munmap(data, fileInfo.st_size);
close(fd);
close(wfd);
return(0);
}
_______________________________________________
Open-graphics mailing list
[email protected]
http://lists.duskglow.com/mailman/listinfo/open-graphics
List service provided by Duskglow Consulting, LLC (www.duskglow.com)
