Skills needed to complete this assignment: Using conditionals and loops Writing
ID: 3886970 • Letter: S
Question
Skills needed to complete this assignment:
Using conditionals and loops
Writing functions
Storing values in vectors, and representing 2D matrices in 1D vectors
The mathematician John Horton Conway invented the “Game of Life” (not the board game). Though not a “game” in any traditional sense, it provides interesting behavior that is specified with only a few rules. This homework asks you to write a program that allows you to specify an initial configuration. The program follows the rules of LIFE to show the continuing behavior of the configuration.
LIFE is an organism that lives in a discrete, two-dimensional world. While this world is actually unlimited, we don’t have that luxury, so we restrict the world to 80 characters wide by 22 character positions high. If you have access to a larger screen, by all means use it. It is your choice to make the edges “wrap around” or not.
This world is a 1D or 2D vector (of char or bool perhaps) with each cell capable of holding one LIFE cell. Generations mark the passing of time. Each generation brings births and deaths to the LIFE community. The births and deaths follow the following set of rules.
We define each cell to have eight neighbor cells. The neighbors of a cell are the cells directly above, below, to the right, to the left, diagonally above to the right and left, and diagonally below to the right and left. Be careful when checking for neighbors on the edges; you can decide whether an edge cell has alive or dead neighbors beyond the edge.
If an occupied cell has zero or one neighbors, it dies of loneliness. If an occupied cell has more than three neighbors, it dies of overcrowding.
If an empty cell has exactly three occupied neighbor cells, there is a birth of a new cell to replace the empty cell.
Births and deaths are instantaneous and occur at the changes of generation. A cell dying for whatever reason may help cause birth, but a new born cell cannot resurrect a cell that is dying, nor will a cell’s death prevent the death of another, say, by reducing the local population.
These may prove interesting starting conditions (see Wikipedia for more options).
F-pentomino
Diehard
Acorn
You will “hard code” a starting configuration. The user need not be able to provide a different starting configuration (that would just complicate your program).
Suggestions: Look for stable configurations. That is, look for communities that repeat patterns continually. The number of configurations in the repetition is called the period. There are configurations that are fixed, which continue without change. A possible project is to find such configurations.
Hints: Define a void function named generation that takes the vector we call world (call-by-reference or using a pointer), which contains the current (or initial) configuration. The function scans the vector and modifies the cells, marking the cells with births and deaths in accord with the rules listed earlier. This involves examining each cell in turn, either killing the cell, letting it live, or if the cell is empty, deciding whether a cell should be born. Note that the game will not work if your code counts neighbors in the same vector it is modifying. A copy of the world vector must be created before it is modified, and this copy is used to count neighbors, while cells are turned on or off in the original vector.
There should be a function display that accepts the vector world and displays the grid on the screen. Some sort of time delay is appropriate between calls to generation and display. To do this, your program should generate and display the next generation when you press Return/Enter. You are at liberty to automate this (put in a real time delay, and not wait for the user to press a key), but automation is not necessary for the program.
If you want to “delay” the display of your grid, rather than wait for the user to type something and press enter before displaying the next grid, then you will need to pause or “sleep” your program somehow. If you are using Microsoft Windows, do this:
On Linux or Mac OS X, do this:
Go to http://www.qotile.net/blog/wp/?p=600 to see some cool 3D visualizations of the game over time. A ridiculous amount of further information is available here: http://www.conwaylife.com/wiki/index.php?title=Main_Page
Download Golly (for Windows, Mac, Linux) to play with cellular automata and some amazing creations by researchers.
Here is an app that generates music based on cellular automata principles: Otmata.
Cellular automata is serious research; see a list of journals that publish articles about cellular automata.
Code template for the homework using vectors (to be precise, a vector of vector of char). This is an outline for just one of the many possible ways of tackling this problem. You are, of course, free to use any method you are comfortable with, so long as the program simulates Conway’s Game of Life.
Still lifes Block Beehive Loaf Boat Oscillators Blinker Toad Beacon Pulsar Spaceships Glider Lightweight spaceshipExplanation / Answer
//main.c
#include<iostream>
#include<vector>
#include<ctime>
#include "gif_hash.h"
#include "gif_hash.c"
#include "gifalloc.c"
#include "egif_lib.c"
#include<unistd.h> // linux
#define ROWS 50
#define COLS 50
#define DEAD ' '
#define ALIVE '*'
#define GIFMULTIPLIER 12
#define GRIDWIDTH 3
using namespace std;
class Square{
public:
char status;
unsigned char color;
};
GifFileType * file;
int useGif = 0;
int gifCycles = 0;
void initGif();
void closeGif();
int how_many_monsters(int row, int col, int radius, vector< vector<Square> > &world);
void generation(vector< vector<Square> > &world, vector< vector<Square> > &world_copy);
void display(vector< vector<Square> > &world);
//Set up the game
int main()
{
srand(time(0));
vector< vector<Square> > world(ROWS, vector<Square>(COLS));
vector< vector<Square> > copy(ROWS, vector<Square>(COLS));
//Randomize colors/statuses
for(int i = 0; i < ROWS; i++){
for(int j = 0; j < COLS; j++){
world[i][j].color = (rand()%254)+2;
world[i][j].status = DEAD;
}
}
//Block
world[2][2].status = world[2][3].status = world[3][3].status = world[3][2].status = ALIVE;
//Beehive
world[2][10].status = world[2][11].status = world[3][9].status = world[3][12].status = ALIVE;
world[4][10].status = world[4][11].status = ALIVE;
//Loaf
world[2][20].status = world[2][21].status = world[3][19].status = world[3][22].status = ALIVE;
world[4][20].status = world[4][22].status = world[5][21].status = ALIVE;
//Boat
world[2][30].status = world[2][31].status = world[3][30].status = world[3][32].status = ALIVE;
world[4][31].status = ALIVE;
//Blinker
world[2][45].status = world[2][46].status = world[2][47].status = ALIVE;
//Toad
world[15][45].status = world[15][46].status = world[15][47].status = ALIVE;
world[16][44].status = world[16][45].status = world[16][46].status = ALIVE;
//Beacon
world[15][30].status = world[15][31].status = world[16][30].status = world[16][31].status = ALIVE;
world[17][32].status = world[17][33].status = world[18][32].status = world[18][33].status = ALIVE;
//Pulsar
world[25][15].status = world[25][16].status = world[25][17].status = world[25][21].status = ALIVE;
world[25][22].status = world[25][23].status = world[30][22].status = world[30][23].status = ALIVE;
world[27][13].status = world[27][18].status = world[27][20].status = world[27][25].status = ALIVE;
world[28][13].status = world[28][18].status = world[28][20].status = world[28][25].status = ALIVE;
world[29][13].status = world[29][18].status = world[29][20].status = world[29][25].status = ALIVE;
world[30][15].status = world[30][16].status = world[30][17].status = world[30][21].status = ALIVE;
world[32][15].status = world[32][16].status = world[32][17].status = world[32][21].status = ALIVE;
world[32][22].status = world[32][23].status = world[37][22].status = world[37][23].status = ALIVE;
world[33][13].status = world[33][18].status = world[33][20].status = world[33][25].status = ALIVE;
world[34][13].status = world[34][18].status = world[34][20].status = world[34][25].status = ALIVE;
world[35][13].status = world[35][18].status = world[35][20].status = world[35][25].status = ALIVE;
world[37][15].status = world[37][16].status = world[37][17].status = world[37][21].status = ALIVE;
//Glider
world[15][15].status = world[16][16].status = world[17][14].status = world[17][15].status = ALIVE;
world[17][16].status = ALIVE;
//Blinker
world[15][0].status = world[15][1].status = world[15][2].status = ALIVE;
//Lightweight Spaceship
world[25][40].status = world[25][41].status = world[25][42].status = world[25][43].status = ALIVE;
world[26][39].status = world[26][43].status = world[27][43].status = world[28][42].status = ALIVE;
world[28][39].status = ALIVE;
//F-pentomino
world[40][40].status = world[40][41].status = world[41][40].status = world[41][39].status = ALIVE;
world[42][40].status = ALIVE;
cout << "Would you also like to output to an image, output.gif (1 = yes)? ";
cin >> useGif;
if(useGif){
cout << "How many cycles do you want to record? ";
cin >> gifCycles;
initGif();
}
while(1)
{
//Clear screen, display world, and wait for some time
system("clear");
display(world);
usleep(800000);
//Update the world
generation(world, copy);
}
//Good practice
world.clear();
copy.clear();
return 0;
}
int how_many_monsters(int row, int col, int radius, vector< vector<Square> > &world){
//Start at top left node
int furthestLeft = col-radius;
int furthestTop = row-radius;
int count = 0;
//Don't count node itself
if(world[row][col].status == ALIVE){
count = -1;
}
//Count cols and rows
for(int i = 0; i < radius*2+1; i++){
row = furthestTop+i;
if(row >= 0 && row < ROWS){
for(int j = 0; j < radius*2+1; j++){
col = furthestLeft+j;
if(col >= 0 && col < COLS){
if(world[row][col].status == ALIVE){
count++;
}
}
}
}
}
//Return count
return count;
}
//See prototype
void generation(vector< vector<Square> > &world,
vector< vector<Square> > &world_copy)
{
// copy the contents of world into world_copy
for(int i = 0; i < ROWS; i++) {
for(int j = 0; j < COLS; j++) {
//Count how many neighbors a cell has
int neighbours = how_many_monsters(i,j,1,world);
//Dies of loneliness or overcrowding
if(world[i][j].status == ALIVE){
if(neighbours <= 1 || neighbours > 3){
world_copy[i][j].status = DEAD;
}else{
world_copy[i][j].status = world[i][j].status;
}
}else{ //Birth
if(neighbours == 3){
world_copy[i][j].status = ALIVE;
}else{
world_copy[i][j].status = world[i][j].status;
}
}
//Preserve colors
world_copy[i][j].color = world[i][j].color;
}
}
//Update world
world = world_copy;
}
//See prototype
void display(vector< vector<Square> > &world)
{
//Set cells alive/dead
int i;
//Get GIF headers ready
if(useGif){
gifCycles--;
if(gifCycles == -1){
closeGif();
useGif = 0;
}else{
EGifPutExtension(file, GRAPHICS_EXT_FUNC_CODE, 4, "d");
EGifPutImageDesc(file, 0, 0, COLS*GIFMULTIPLIER+GRIDWIDTH, ROWS*GIFMULTIPLIER+GRIDWIDTH, 0, NULL);
}
}
//Display game of status!
for(i = 0; i < ROWS; i++){
//Display to terminal
for(int j = 0; j < COLS; j++){
cout << (char)world[i][j].status;
}
//Display to gif
if(useGif){
for(int k = 0; k < GIFMULTIPLIER; k++){ //Start rows
if(k > GRIDWIDTH-1){
for(int j = 0; j < COLS; j++){ //Draw columns of each row
for(int z = 0; z < GRIDWIDTH; z++){
EGifPutPixel(file, 0); //Vertical grid outline
}
if(world[i][j].status == ALIVE){
for(int l = 0; l < GIFMULTIPLIER-GRIDWIDTH; l++){
EGifPutPixel(file, world[i][j].color); //Draw alive pixel
}
}else{
for(int l = 0; l < GIFMULTIPLIER-GRIDWIDTH; l++){
EGifPutPixel(file, 1); //Draw dead pixel
}
}
}
}else{ //horizontal grid outline
for(int j = 0; j < COLS*GIFMULTIPLIER; j++){
EGifPutPixel(file, 0); //Draw grid
}
}
for(int z = 0; z < GRIDWIDTH; z++){
EGifPutPixel(file, 0); //Closing vertical grid outline
}
}
}
cout << endl;
}
//Finish drawing the grid if we're doing GIF output
if(useGif){
for(int j = 0; j < (COLS*GIFMULTIPLIER+GRIDWIDTH)*GRIDWIDTH; j++){ //Closing horizontal grid outline
EGifPutPixel(file, 0);
}
}
}
//See prototype
void initGif(){
//Make color map
ColorMapObject *GIFcmap;
GIFcmap = GifMakeMapObject(256, NULL);
GIFcmap->Colors[0].Red = 0;
GIFcmap->Colors[0].Green = 0;
GIFcmap->Colors[0].Blue = 0;
GIFcmap->Colors[1].Red = 255;
GIFcmap->Colors[1].Green = 255;
GIFcmap->Colors[1].Blue = 255;
//Randomize color map
for(int i = 0; i < 254; i++){
switch(rand()%3){
case 0:
GIFcmap->Colors[i+2].Red = 255;
GIFcmap->Colors[i+2].Green = rand()%128;
GIFcmap->Colors[i+2].Blue = rand()%128;
break;
case 1:
GIFcmap->Colors[i+2].Red = rand()%128;
GIFcmap->Colors[i+2].Green = 255;
GIFcmap->Colors[i+2].Blue = rand()%128;
break;
case 2:
GIFcmap->Colors[i+2].Red = rand()%128;
GIFcmap->Colors[i+2].Green = rand()%128;
GIFcmap->Colors[i+2].Blue = 255;
break;
}
}
//Initialize GIF header
char * fileName = "output.gif";
file = EGifOpenFileName(fileName, false, NULL);
EGifPutScreenDesc(file, COLS*GIFMULTIPLIER+GRIDWIDTH, ROWS*GIFMULTIPLIER+GRIDWIDTH, 256, 1, GIFcmap);
EGifPutExtensionLeader(file, APPLICATION_EXT_FUNC_CODE);
EGifPutExtensionBlock(file, 11, "NETSCAPE2.0");
EGifPutExtensionBlock(file, 3, "");
EGifPutExtensionTrailer(file);
}
//See prototype
void closeGif(){
//Close GIF file
EGifCloseFile(file);
}
================================================================================
//gifalloc.c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include "gif_lib.h"
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
int
GifBitSize(int n)
{
register int i;
for (i = 1; i <= 8; i++)
if ((1 << i) >= n)
break;
return (i);
}
ColorMapObject *
GifMakeMapObject(int ColorCount, const GifColorType *ColorMap)
{
ColorMapObject *Object;
if (ColorCount != (1 << GifBitSize(ColorCount))) {
return ((ColorMapObject *) NULL);
}
Object = (ColorMapObject *)malloc(sizeof(ColorMapObject));
if (Object == (ColorMapObject *) NULL) {
return ((ColorMapObject *) NULL);
}
Object->Colors = (GifColorType *)calloc(ColorCount, sizeof(GifColorType));
if (Object->Colors == (GifColorType *) NULL) {
free(Object);
return ((ColorMapObject *) NULL);
}
Object->ColorCount = ColorCount;
Object->BitsPerPixel = GifBitSize(ColorCount);
if (ColorMap != NULL) {
memcpy((char *)Object->Colors,
(char *)ColorMap, ColorCount * sizeof(GifColorType));
}
return (Object);
}
/*******************************************************************************
Free a color map object
*******************************************************************************/
void
GifFreeMapObject(ColorMapObject *Object)
{
if (Object != NULL) {
(void)free(Object->Colors);
(void)free(Object);
}
}
#ifdef DEBUG
void
DumpColorMap(ColorMapObject *Object,
FILE * fp)
{
if (Object != NULL) {
int i, j, Len = Object->ColorCount;
for (i = 0; i < Len; i += 4) {
for (j = 0; j < 4 && j < Len; j++) {
(void)fprintf(fp, "%3d: %02x %02x %02x ", i + j,
Object->Colors[i + j].Red,
Object->Colors[i + j].Green,
Object->Colors[i + j].Blue);
}
(void)fprintf(fp, " ");
}
}
}
#endif
ColorMapObject *
GifUnionColorMap(const ColorMapObject *ColorIn1,
const ColorMapObject *ColorIn2,
GifPixelType ColorTransIn2[])
{
int i, j, CrntSlot, RoundUpTo, NewGifBitSize;
ColorMapObject *ColorUnion;
ColorUnion = GifMakeMapObject(MAX(ColorIn1->ColorCount,
ColorIn2->ColorCount) * 2, NULL);
if (ColorUnion == NULL)
return (NULL);
/*
* Copy ColorIn1 to ColorUnion.
*/
for (i = 0; i < ColorIn1->ColorCount; i++)
ColorUnion->Colors[i] = ColorIn1->Colors[i];
CrntSlot = ColorIn1->ColorCount;
while (ColorIn1->Colors[CrntSlot - 1].Red == 0
&& ColorIn1->Colors[CrntSlot - 1].Green == 0
&& ColorIn1->Colors[CrntSlot - 1].Blue == 0)
CrntSlot--;
for (i = 0; i < ColorIn2->ColorCount && CrntSlot <= 256; i++) {
/* Let's see if this color already exists: */
for (j = 0; j < ColorIn1->ColorCount; j++)
if (memcmp (&ColorIn1->Colors[j], &ColorIn2->Colors[i],
sizeof(GifColorType)) == 0)
break;
if (j < ColorIn1->ColorCount)
ColorTransIn2[i] = j; /* color exists in Color1 */
else {
/* Color is new - copy it to a new slot: */
ColorUnion->Colors[CrntSlot] = ColorIn2->Colors[i];
ColorTransIn2[i] = CrntSlot++;
}
}
if (CrntSlot > 256) {
GifFreeMapObject(ColorUnion);
return ((ColorMapObject *) NULL);
}
NewGifBitSize = GifBitSize(CrntSlot);
RoundUpTo = (1 << NewGifBitSize);
if (RoundUpTo != ColorUnion->ColorCount) {
register GifColorType *Map = ColorUnion->Colors;
for (j = CrntSlot; j < RoundUpTo; j++)
Map[j].Red = Map[j].Green = Map[j].Blue = 0;
/* perhaps we can shrink the map? */
if (RoundUpTo < ColorUnion->ColorCount)
ColorUnion->Colors = (GifColorType *)realloc(Map,
sizeof(GifColorType) * RoundUpTo);
}
ColorUnion->ColorCount = RoundUpTo;
ColorUnion->BitsPerPixel = NewGifBitSize;
return (ColorUnion);
}
/*******************************************************************************
Apply a given color translation to the raster bits of an image
*******************************************************************************/
void
GifApplyTranslation(SavedImage *Image, GifPixelType Translation[])
{
register int i;
register int RasterSize = Image->ImageDesc.Height * Image->ImageDesc.Width;
for (i = 0; i < RasterSize; i++)
Image->RasterBits[i] = Translation[Image->RasterBits[i]];
}
/******************************************************************************
Extension record functions
******************************************************************************/
int
GifAddExtensionBlock(int *ExtensionBlockCount,
ExtensionBlock **ExtensionBlocks,
int Function,
unsigned int Len,
unsigned char ExtData[])
{
ExtensionBlock *ep;
if (*ExtensionBlocks == NULL)
*ExtensionBlocks=(ExtensionBlock *)malloc(sizeof(ExtensionBlock));
else
*ExtensionBlocks = (ExtensionBlock *)realloc(*ExtensionBlocks,
sizeof(ExtensionBlock) *
(*ExtensionBlockCount + 1));
if (*ExtensionBlocks == NULL)
return (GIF_ERROR);
ep = &(*ExtensionBlocks)[(*ExtensionBlockCount)++];
ep->Function = Function;
ep->ByteCount=Len;
ep->Bytes = (GifByteType *)malloc(ep->ByteCount);
if (ep->Bytes == NULL)
return (GIF_ERROR);
if (ExtData != NULL) {
memcpy(ep->Bytes, ExtData, Len);
}
return (GIF_OK);
}
void
GifFreeExtensions(int *ExtensionBlockCount,
ExtensionBlock **ExtensionBlocks)
{
ExtensionBlock *ep;
if (*ExtensionBlocks == NULL)
return;
for (ep = *ExtensionBlocks;
ep < (*ExtensionBlocks + *ExtensionBlockCount);
ep++)
(void)free((char *)ep->Bytes);
(void)free((char *)*ExtensionBlocks);
*ExtensionBlocks = NULL;
*ExtensionBlockCount = 0;
}
void
FreeLastSavedImage(GifFileType *GifFile)
{
SavedImage *sp;
if ((GifFile == NULL) || (GifFile->SavedImages == NULL))
return;
/* Remove one SavedImage from the GifFile */
GifFile->ImageCount--;
sp = &GifFile->SavedImages[GifFile->ImageCount];
/* Deallocate its Colormap */
if (sp->ImageDesc.ColorMap != NULL) {
GifFreeMapObject(sp->ImageDesc.ColorMap);
sp->ImageDesc.ColorMap = NULL;
}
/* Deallocate the image data */
if (sp->RasterBits != NULL)
free((char *)sp->RasterBits);
/* Deallocate any extensions */
GifFreeExtensions(&sp->ExtensionBlockCount, &sp->ExtensionBlocks);
}
SavedImage *
GifMakeSavedImage(GifFileType *GifFile, const SavedImage *CopyFrom)
{
SavedImage *sp;
if (GifFile->SavedImages == NULL)
GifFile->SavedImages = (SavedImage *)malloc(sizeof(SavedImage));
else
GifFile->SavedImages = (SavedImage *)realloc(GifFile->SavedImages,
sizeof(SavedImage) * (GifFile->ImageCount + 1));
if (GifFile->SavedImages == NULL)
return ((SavedImage *)NULL);
else {
sp = &GifFile->SavedImages[GifFile->ImageCount++];
memset((char *)sp, '', sizeof(SavedImage));
if (CopyFrom != NULL) {
memcpy((char *)sp, CopyFrom, sizeof(SavedImage));
if (sp->ImageDesc.ColorMap != NULL) {
sp->ImageDesc.ColorMap = GifMakeMapObject(
CopyFrom->ImageDesc.ColorMap->ColorCount,
CopyFrom->ImageDesc.ColorMap->Colors);
if (sp->ImageDesc.ColorMap == NULL) {
FreeLastSavedImage(GifFile);
return (SavedImage *)(NULL);
}
}
/* next, the raster */
sp->RasterBits = (unsigned char *)malloc(sizeof(GifPixelType) *
CopyFrom->ImageDesc.Height *
CopyFrom->ImageDesc.Width);
if (sp->RasterBits == NULL) {
FreeLastSavedImage(GifFile);
return (SavedImage *)(NULL);
}
memcpy(sp->RasterBits, CopyFrom->RasterBits,
sizeof(GifPixelType) * CopyFrom->ImageDesc.Height *
CopyFrom->ImageDesc.Width);
/* finally, the extension blocks */
if (sp->ExtensionBlocks != NULL) {
sp->ExtensionBlocks = (ExtensionBlock *)malloc(
sizeof(ExtensionBlock) *
CopyFrom->ExtensionBlockCount);
if (sp->ExtensionBlocks == NULL) {
FreeLastSavedImage(GifFile);
return (SavedImage *)(NULL);
}
memcpy(sp->ExtensionBlocks, CopyFrom->ExtensionBlocks,
sizeof(ExtensionBlock) * CopyFrom->ExtensionBlockCount);
}
}
return (sp);
}
}
void
GifFreeSavedImages(GifFileType *GifFile)
{
SavedImage *sp;
if ((GifFile == NULL) || (GifFile->SavedImages == NULL)) {
return;
}
for (sp = GifFile->SavedImages;
sp < GifFile->SavedImages + GifFile->ImageCount; sp++) {
if (sp->ImageDesc.ColorMap != NULL) {
GifFreeMapObject(sp->ImageDesc.ColorMap);
sp->ImageDesc.ColorMap = NULL;
}
if (sp->RasterBits != NULL)
free((char *)sp->RasterBits);
GifFreeExtensions(&sp->ExtensionBlockCount, &sp->ExtensionBlocks);
}
free((char *)GifFile->SavedImages);
GifFile->SavedImages = NULL;
}
/* end */
============================================================================
//gif_lib_private.h
#ifndef _GIF_LIB_PRIVATE_H
#define _GIF_LIB_PRIVATE_H
#include "gif_lib.h"
#include "gif_hash.h"
#define EXTENSION_INTRODUCER 0x21
#define DESCRIPTOR_INTRODUCER 0x2c
#define TERMINATOR_INTRODUCER 0x3b
#define LZ_MAX_CODE 4095 /* Biggest code possible in 12 bits. */
#define LZ_BITS 12
#define FLUSH_OUTPUT 4096 /* Impossible code, to signal flush. */
#define FIRST_CODE 4097 /* Impossible code, to signal first. */
#define NO_SUCH_CODE 4098 /* Impossible code, to signal empty. */
#define FILE_STATE_WRITE 0x01
#define FILE_STATE_SCREEN 0x02
#define FILE_STATE_IMAGE 0x04
#define FILE_STATE_READ 0x08
#define IS_READABLE(Private) (Private->FileState & FILE_STATE_READ)
#define IS_WRITEABLE(Private) (Private->FileState & FILE_STATE_WRITE)
typedef struct GifFilePrivateType {
GifWord FileState, FileHandle,
BitsPerPixel,
ClearCode,
EOFCode,
RunningCode,
RunningBits,
MaxCode1,
LastCode,
CrntCode,
StackPtr,
CrntShiftState;
unsigned long CrntShiftDWord;
unsigned long PixelCount;
FILE *File;
InputFunc Read;
OutputFunc Write;
GifByteType Buf[256];
GifByteType Stack[LZ_MAX_CODE];
GifByteType Suffix[LZ_MAX_CODE + 1];
GifPrefixType Prefix[LZ_MAX_CODE + 1];
GifHashTableType *HashTable;
bool gif89;
} GifFilePrivateType;
#endif
=============================================================================
//gif_lib.h
#ifndef _GIF_LIB_H_
#define _GIF_LIB_H_ 1
#ifdef __cplusplus
extern "C" {
#endif /* __cplusplus */
#define GIFLIB_MAJOR 5
#define GIFLIB_MINOR 0
#define GIFLIB_RELEASE 0
#define GIF_ERROR 0
#define GIF_OK 1
#include <stdbool.h>
#define GIF_STAMP "GIFVER"
#define GIF_STAMP_LEN sizeof(GIF_STAMP) - 1
#define GIF_VERSION_POS 3
#define GIF87_STAMP "GIF87a"
#define GIF89_STAMP "GIF89a"
typedef unsigned char GifPixelType;
typedef unsigned char *GifRowType;
typedef unsigned char GifByteType;
typedef unsigned int GifPrefixType;
typedef int GifWord;
typedef struct GifColorType {
GifByteType Red, Green, Blue;
} GifColorType;
typedef struct ColorMapObject {
int ColorCount;
int BitsPerPixel;
bool SortFlag;
GifColorType *Colors; /* on malloc(3) heap */
} ColorMapObject;
typedef struct GifImageDesc {
GifWord Left, Top, Width, Height; /* Current image dimensions. */
bool Interlace; /* Sequential/Interlaced lines. */
ColorMapObject *ColorMap; /* The local color map */
} GifImageDesc;
typedef struct ExtensionBlock {
int ByteCount;
GifByteType *Bytes; /* on malloc(3) heap */
int Function; /* The block function code */
#define CONTINUE_EXT_FUNC_CODE 0x00 /* continuation subblock */
#define COMMENT_EXT_FUNC_CODE 0xfe /* comment */
#define GRAPHICS_EXT_FUNC_CODE 0xf9 /* graphics control (GIF89) */
#define PLAINTEXT_EXT_FUNC_CODE 0x01 /* plaintext */
#define APPLICATION_EXT_FUNC_CODE 0xff /* application block */
} ExtensionBlock;
typedef struct SavedImage {
GifImageDesc ImageDesc;
GifByteType *RasterBits;
int ExtensionBlockCount;
ExtensionBlock *ExtensionBlocks;
} SavedImage;
typedef struct GifFileType {
GifWord SWidth, SHeight;
GifWord SColorResolution;
GifWord SBackGroundColor;
GifByteType AspectByte;
ColorMapObject *SColorMap;
int ImageCount;
GifImageDesc Image;
SavedImage *SavedImages;
int ExtensionBlockCount;
ExtensionBlock *ExtensionBlocks;
int Error;
void *UserData;
void *Private; /* Don't mess with this! */
} GifFileType;
#define GIF_ASPECT_RATIO(n) ((n)+15.0/64.0)
typedef enum {
UNDEFINED_RECORD_TYPE,
SCREEN_DESC_RECORD_TYPE,
IMAGE_DESC_RECORD_TYPE, /* Begin with ',' */
EXTENSION_RECORD_TYPE, /* Begin with '!' */
TERMINATE_RECORD_TYPE /* Begin with ';' */
} GifRecordType;
/* func type to read gif data from arbitrary sources (TVT) */
typedef int (*InputFunc) (GifFileType *, GifByteType *, int);
/* func type to write gif data to arbitrary targets.
* Returns count of bytes written. (MRB)
*/
typedef int (*OutputFunc) (GifFileType *, const GifByteType *, int);
/******************************************************************************
GIF89 structures
******************************************************************************/
typedef struct GraphicsControlBlock {
int DisposalMode;
#define DISPOSAL_UNSPECIFIED 0 /* No disposal specified. */
#define DISPOSE_DO_NOT 1 /* Leave image in place */
#define DISPOSE_BACKGROUND 2 /* Set area too background color */
#define DISPOSE_PREVIOUS 3 /* Restore to previous content */
bool UserInputFlag; /* User confirmation required before disposal */
int DelayTime; /* pre-display delay in 0.01sec units */
int TransparentColor; /* Palette index for transparency, -1 if none */
#define NO_TRANSPARENT_COLOR -1
} GraphicsControlBlock;
/******************************************************************************
GIF encoding routines
******************************************************************************/
/* Main entry points */
GifFileType *EGifOpenFileName(const char *GifFileName,
const bool GifTestExistence, int *Error);
GifFileType *EGifOpenFileHandle(const int GifFileHandle, int *Error);
GifFileType *EGifOpen(void *userPtr, OutputFunc writeFunc, int *Error);
int EGifSpew(GifFileType * GifFile);
char *EGifGetGifVersion(GifFileType *GifFile); /* new in 5.x */
int EGifCloseFile(GifFileType * GifFile);
#define E_GIF_ERR_OPEN_FAILED 1 /* And EGif possible errors. */
#define E_GIF_ERR_WRITE_FAILED 2
#define E_GIF_ERR_HAS_SCRN_DSCR 3
#define E_GIF_ERR_HAS_IMAG_DSCR 4
#define E_GIF_ERR_NO_COLOR_MAP 5
#define E_GIF_ERR_DATA_TOO_BIG 6
#define E_GIF_ERR_NOT_ENOUGH_MEM 7
#define E_GIF_ERR_DISK_IS_FULL 8
#define E_GIF_ERR_CLOSE_FAILED 9
#define E_GIF_ERR_NOT_WRITEABLE 10
/* These are legacy. You probably do not want to call them directly */
int EGifPutScreenDesc(GifFileType *GifFile,
const int GifWidth, const int GifHeight,
const int GifColorRes,
const int GifBackGround,
const ColorMapObject *GifColorMap);
int EGifPutImageDesc(GifFileType *GifFile,
const int GifLeft, const int GifTop,
const int GifWidth, const int GifHeight,
const bool GifInterlace,
const ColorMapObject *GifColorMap);
int EGifPutLine(GifFileType *GifFile, GifPixelType *GifLine,
int GifLineLen);
int EGifPutPixel(GifFileType *GifFile, const GifPixelType GifPixel);
int EGifPutComment(GifFileType *GifFile, const char *GifComment);
int EGifPutExtensionLeader(GifFileType *GifFile, const int GifExtCode);
int EGifPutExtensionBlock(GifFileType *GifFile,
const int GifExtLen, const void *GifExtension);
int EGifPutExtensionTrailer(GifFileType *GifFile);
int EGifPutExtension(GifFileType *GifFile, const int GifExtCode,
const int GifExtLen,
const void *GifExtension);
int EGifPutCode(GifFileType *GifFile, int GifCodeSize,
const GifByteType *GifCodeBlock);
int EGifPutCodeNext(GifFileType *GifFile,
const GifByteType *GifCodeBlock);
/******************************************************************************
GIF decoding routines
******************************************************************************/
/* Main entry points */
GifFileType *DGifOpenFileName(const char *GifFileName, int *Error);
GifFileType *DGifOpenFileHandle(int GifFileHandle, int *Error);
int DGifSlurp(GifFileType * GifFile);
GifFileType *DGifOpen(void *userPtr, InputFunc readFunc, int *Error); /* new one (TVT) */
int DGifCloseFile(GifFileType * GifFile);
#define D_GIF_ERR_OPEN_FAILED 101 /* And DGif possible errors. */
#define D_GIF_ERR_READ_FAILED 102
#define D_GIF_ERR_NOT_GIF_FILE 103
#define D_GIF_ERR_NO_SCRN_DSCR 104
#define D_GIF_ERR_NO_IMAG_DSCR 105
#define D_GIF_ERR_NO_COLOR_MAP 106
#define D_GIF_ERR_WRONG_RECORD 107
#define D_GIF_ERR_DATA_TOO_BIG 108
#define D_GIF_ERR_NOT_ENOUGH_MEM 109
#define D_GIF_ERR_CLOSE_FAILED 110
#define D_GIF_ERR_NOT_READABLE 111
#define D_GIF_ERR_IMAGE_DEFECT 112
#define D_GIF_ERR_EOF_TOO_SOON 113
/* These are legacy. You probably do not want to call them directly */
int DGifGetScreenDesc(GifFileType *GifFile);
int DGifGetRecordType(GifFileType *GifFile, GifRecordType *GifType);
int DGifGetImageDesc(GifFileType *GifFile);
int DGifGetLine(GifFileType *GifFile, GifPixelType *GifLine, int GifLineLen);
int DGifGetPixel(GifFileType *GifFile, GifPixelType GifPixel);
int DGifGetComment(GifFileType *GifFile, char *GifComment);
int DGifGetExtension(GifFileType *GifFile, int *GifExtCode,
GifByteType **GifExtension);
int DGifGetExtensionNext(GifFileType *GifFile, GifByteType **GifExtension);
int DGifGetCode(GifFileType *GifFile, int *GifCodeSize,
GifByteType **GifCodeBlock);
int DGifGetCodeNext(GifFileType *GifFile, GifByteType **GifCodeBlock);
int DGifGetLZCodes(GifFileType *GifFile, int *GifCode);
/******************************************************************************
Color table quantization (deprecated)
******************************************************************************/
int GifQuantizeBuffer(unsigned int Width, unsigned int Height,
int *ColorMapSize, GifByteType * RedInput,
GifByteType * GreenInput, GifByteType * BlueInput,
GifByteType * OutputBuffer,
GifColorType * OutputColorMap);
/******************************************************************************
Error handling and reporting.
******************************************************************************/
extern char *GifErrorString(int ErrorCode); /* new in 2012 - ESR */
extern ColorMapObject *GifMakeMapObject(int ColorCount,
const GifColorType *ColorMap);
extern void GifFreeMapObject(ColorMapObject *Object);
extern ColorMapObject *GifUnionColorMap(const ColorMapObject *ColorIn1,
const ColorMapObject *ColorIn2,
GifPixelType ColorTransIn2[]);
extern int GifBitSize(int n);
/******************************************************************************
Support for the in-core structures allocation (slurp mode).
******************************************************************************/
extern void GifApplyTranslation(SavedImage *Image, GifPixelType Translation[]);
extern int GifAddExtensionBlock(int *ExtensionBlock_Count,
ExtensionBlock **ExtensionBlocks,
int Function,
unsigned int Len, unsigned char ExtData[]);
extern void GifFreeExtensions(int *ExtensionBlock_Count,
ExtensionBlock **ExtensionBlocks);
extern SavedImage *GifMakeSavedImage(GifFileType *GifFile,
const SavedImage *CopyFrom);
extern void GifFreeSavedImages(GifFileType *GifFile);
/******************************************************************************
5.x functions for GIF89 graphics control blocks
******************************************************************************/
int DGifExtensionToGCB(const size_t GifExtensionLength,
const GifByteType *GifExtension,
GraphicsControlBlock *GCB);
size_t EGifGCBToExtension(const GraphicsControlBlock *GCB,
GifByteType *GifExtension);
int DGifSavedExtensionToGCB(GifFileType *GifFile,
int ImageIndex,
GraphicsControlBlock *GCB);
int EGifGCBToSavedExtension(const GraphicsControlBlock *GCB,
GifFileType *GifFile,
int ImageIndex);
/******************************************************************************
The library's internal utility font
******************************************************************************/
#define GIF_FONT_WIDTH 8
#define GIF_FONT_HEIGHT 8
extern const unsigned char GifAsciiTable8x8[][GIF_FONT_WIDTH];
extern void GifDrawText8x8(SavedImage *Image,
const int x, const int y,
const char *legend, const int color);
extern void GifDrawBox(SavedImage *Image,
const int x, const int y,
const int w, const int d, const int color);
extern void GifDrawRectangle(SavedImage *Image,
const int x, const int y,
const int w, const int d, const int color);
extern void GifDrawBoxedText8x8(SavedImage *Image,
const int x, const int y,
const char *legend,
const int border, const int bg, const int fg);
#ifdef __cplusplus
}
#endif /* __cplusplus */
#endif /* _GIF_LIB_H */
/* end */
==============================================================================
//gif_hash.h
#ifndef _GIF_HASH_H_
#define _GIF_HASH_H_
#include <unistd.h>
#include <stdint.h>
#define HT_SIZE 8192 /* 12bits = 4096 or twice as big! */
#define HT_KEY_MASK 0x1FFF /* 13bits keys */
#define HT_KEY_NUM_BITS 13 /* 13bits keys */
#define HT_MAX_KEY 8191 /* 13bits - 1, maximal code possible */
#define HT_MAX_CODE 4095 /* Biggest code possible in 12 bits. */
#define HT_GET_KEY(l) (l >> 12)
#define HT_GET_CODE(l) (l & 0x0FFF)
#define HT_PUT_KEY(l) (l << 12)
#define HT_PUT_CODE(l) (l & 0x0FFF)
typedef struct GifHashTableType {
uint32_t HTable[HT_SIZE];
} GifHashTableType;
GifHashTableType *_InitHashTable(void);
void _ClearHashTable(GifHashTableType *HashTable);
void _InsertHashTable(GifHashTableType *HashTable, uint32_t Key, int Code);
int _ExistsHashTable(GifHashTableType *HashTable, uint32_t Key);
#endif /* _GIF_HASH_H_ */
/* end */
=========================================================================
//gif_hash.c
#include <unistd.h>
#include <stdint.h>
#include <stdlib.h>
#include <fcntl.h>
#include <stdio.h>
#include <string.h>
#include "gif_lib.h"
#include "gif_hash.h"
#include "gif_lib_private.h"
/* #define DEBUG_HIT_RATE Debug number of misses per hash Insert/Exists. */
#ifdef DEBUG_HIT_RATE
static long NumberOfTests = 0,
NumberOfMisses = 0;
#endif /* DEBUG_HIT_RATE */
static int KeyItem(uint32_t Item);
/******************************************************************************
Initialize HashTable - allocate the memory needed and clear it. *
******************************************************************************/
GifHashTableType *_InitHashTable(void)
{
GifHashTableType *HashTable;
if ((HashTable = (GifHashTableType *) malloc(sizeof(GifHashTableType)))
== NULL)
return NULL;
_ClearHashTable(HashTable);
return HashTable;
}
void _ClearHashTable(GifHashTableType *HashTable)
{
memset(HashTable -> HTable, 0xFF, HT_SIZE * sizeof(uint32_t));
}
void _InsertHashTable(GifHashTableType *HashTable, uint32_t Key, int Code)
{
int HKey = KeyItem(Key);
uint32_t *HTable = HashTable -> HTable;
#ifdef DEBUG_HIT_RATE
NumberOfTests++;
NumberOfMisses++;
#endif /* DEBUG_HIT_RATE */
while (HT_GET_KEY(HTable[HKey]) != 0xFFFFFL) {
#ifdef DEBUG_HIT_RATE
NumberOfMisses++;
#endif /* DEBUG_HIT_RATE */
HKey = (HKey + 1) & HT_KEY_MASK;
}
HTable[HKey] = HT_PUT_KEY(Key) | HT_PUT_CODE(Code);
}
int _ExistsHashTable(GifHashTableType *HashTable, uint32_t Key)
{
int HKey = KeyItem(Key);
uint32_t *HTable = HashTable -> HTable, HTKey;
#ifdef DEBUG_HIT_RATE
NumberOfTests++;
NumberOfMisses++;
#endif /* DEBUG_HIT_RATE */
while ((HTKey = HT_GET_KEY(HTable[HKey])) != 0xFFFFFL) {
#ifdef DEBUG_HIT_RATE
NumberOfMisses++;
#endif /* DEBUG_HIT_RATE */
if (Key == HTKey) return HT_GET_CODE(HTable[HKey]);
HKey = (HKey + 1) & HT_KEY_MASK;
}
return -1;
}
static int KeyItem(uint32_t Item)
{
return ((Item >> 12) ^ Item) & HT_KEY_MASK;
}
#ifdef DEBUG_HIT_RATE
void HashTablePrintHitRatio(void)
{
printf("Hash Table Hit Ratio is %ld/%ld = %ld%%. ",
NumberOfMisses, NumberOfTests,
NumberOfMisses * 100 / NumberOfTests);
}
#endif /* DEBUG_HIT_RATE */
/* end */
==========================================================================
Note:Don't space to copy complete code.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.