Fix: SE047 Problem: XPM tile files are 1-dimentional, creating a very high and narrow image. X11 has a limitation in that it is unable to handle images with dimensions larger than 32767. With the current number of tiles in Slash'EM we can only store them at 24 pixels high before we hit this problem. Vanilla 3.3.0 has 995 tiles, so it too will hit this problem very soon. At the moment the only manifestation of this problem is that the arbitary limits in tile size in the Qt interface have had to be reduced from 32x32 to 32x24 and that if any user follows the XPM expansion example in Install.X11 this will fail above a height of 24. Looking further forward, this problem is also one of the things preventing the inclusion of Mitsuhiro Itakura's 32x32 tile set. The solution is to determine at build time the dimensions of a 2-D array of tiles to use. This means that users can scale tile sets if they want using the example code in Install.X11 without causing problems. (It causes other problems in that the Qt and GTK interfaces both assume that x11tiles contains 16x16 tiles. There is no good reason for this and it should be changed.) Compatible with: Slash'EM 0.0.6E0F1 Author: J. Ali Harlow, ali@avrc.city.ac.uk Date: 1 Feb 2000 *** include/qt_win.h.orig Mon Jan 31 14:53:19 2000 --- include/qt_win.h Fri Jan 28 19:06:52 2000 *************** *** 246,252 **** QImage img; QPixmap pm; QSize size; - int tiles_per_row; }; class BlackScrollView : public QScrollView { --- 246,251 ---- *** win/Qt/qt_win.cpp.orig Mon Jan 31 14:53:19 2000 --- win/Qt/qt_win.cpp Fri Jan 28 19:04:30 2000 *************** *** 187,192 **** --- 187,194 ---- extern const char *hu_stat[]; /* from eat.c */ extern const char *killed_by_prefix[]; extern int total_tiles_used; // from tile.c + extern int tiles_per_row; // from tile.c + extern int tiles_per_col; // from tile.c extern short glyph2tile[]; // from tile.c } *************** *** 249,266 **** " "}; NetHackQtSettings::NetHackQtSettings(int w, int h) : ! tilewidth(TILEWMIN,32,1,this), ! #if 0 ! tileheight(TILEHMIN,32,1,this), ! #else ! /* ! * ALI: Temporary hack to avoid hitting bug with dimensions ! * larger than 32767. This is the comparable problem as to that ! * fixed for X11 in SE001. A similiar solution will probably ! * be required. ! */ ! tileheight(TILEHMIN,24,1,this), ! #endif widthlbl(&tilewidth,"&Width:",this), heightlbl(&tileheight,"&Height:",this), fontsize(this), --- 251,258 ---- " "}; NetHackQtSettings::NetHackQtSettings(int w, int h) : ! tilewidth(TILEWMIN,64,1,this), ! tileheight(TILEHMIN,64,1,this), widthlbl(&tilewidth,"&Width:",this), heightlbl(&tileheight,"&Height:",this), fontsize(this), *************** *** 3493,3507 **** tiles_per_row = 40; } } else { ! tiles_per_row = 1; ! if (img.height()%total_tiles_used) { ! impossible("Tile file \"%s\" has %d lines, not multiple of glyph count (%d)", ! tile_file, img.height(), total_tiles_used); } } - int rows = ((total_tiles_used+tiles_per_row-1) / tiles_per_row); tw = img.width() / tiles_per_row; ! th = img.height() / rows; #ifdef FILE_AREAS free(tile_file); #endif --- 3485,3500 ---- tiles_per_row = 40; } } else { ! if (img.height()%tiles_per_col || img.width()%tiles_per_row) { ! impossible( ! "Tile file \"%s\" appears to have a non-integer tile size.\n" ! "Its size (%dx%d) should be a multiple of %dx%d", ! tile_file, img.width(), img.height(), ! tiles_per_row, tiles_per_col); } } tw = img.width() / tiles_per_row; ! th = img.height() / tiles_per_col; #ifdef FILE_AREAS free(tile_file); #endif *** win/X11/tile2x11.c.orig Mon Jan 31 14:53:08 2000 --- win/X11/tile2x11.c Fri Jan 28 18:10:19 2000 *************** *** 122,128 **** xpm_write(fp) FILE *fp; { ! int i,j,n; if (header.ncolors > 64) { Fprintf(stderr, "Sorry, only configured for up to 64 colors\n"); --- 122,129 ---- xpm_write(fp) FILE *fp; { ! int i,j,x,y; ! unsigned char *bytes; if (header.ncolors > 64) { Fprintf(stderr, "Sorry, only configured for up to 64 colors\n"); *************** *** 133,140 **** fprintf(fp, "/* XPM */\n"); fprintf(fp, "static char* nhtiles[] = {\n"); fprintf(fp, "\"%lu %lu %lu %d\",\n", ! header.tile_width, ! header.tile_height*header.ntiles, header.ncolors, 1 /* char per color */); for (i = 0; i < header.ncolors; i++) --- 134,141 ---- fprintf(fp, "/* XPM */\n"); fprintf(fp, "static char* nhtiles[] = {\n"); fprintf(fp, "\"%lu %lu %lu %d\",\n", ! header.tile_width*TILES_PER_ROW, ! header.tile_height*TILES_PER_COL, header.ncolors, 1 /* char per color */); for (i = 0; i < header.ncolors; i++) *************** *** 144,161 **** x11_colormap[i][1], x11_colormap[i][2]); ! n=0; ! for (i = 0; i < header.tile_height*header.ntiles; i++) { ! fprintf(fp, "\""); ! for (j = 0; j < header.tile_width; j++) { ! /* just one char per color */ ! fputc(tile_bytes[n++]+'0', fp); ! } ! if (j==header.tile_width-1) ! fprintf(fp, "\"\n"); ! else fprintf(fp, "\",\n"); ! } return fprintf(fp, "};\n")>=0; } --- 145,164 ---- x11_colormap[i][1], x11_colormap[i][2]); ! for (j = 0; j < TILES_PER_COL; j++) ! for (y = 0; y < header.tile_height; y++) { ! bytes=tile_bytes+(j*TILES_PER_ROW*header.tile_height+y)* ! header.tile_width; ! fprintf(fp, "\""); ! for (i = 0; i < TILES_PER_ROW; i++) { ! for (x = 0; x < header.tile_width; x++) { ! /* just one char per color */ ! fputc(bytes[x]+'0', fp); ! } ! bytes+=header.tile_height*header.tile_width; ! } fprintf(fp, "\",\n"); ! } return fprintf(fp, "};\n")>=0; } *** win/X11/winmap.c.orig Mon Jan 31 14:53:08 2000 --- win/X11/winmap.c Fri Jan 28 18:51:54 2000 *************** *** 48,53 **** --- 48,55 ---- /* from tile.c */ extern short glyph2tile[]; extern int total_tiles_used; + extern int tiles_per_row; + extern int tiles_per_col; /* Define these if you really want a lot of junk on your screen. */ /* #define VERBOSE */ /* print various info & events as they happen */ *************** *** 217,223 **** static int tile_width; static int tile_height; static int tile_count; - static int tiles_per_line; /* In tile_image & tile_pixmap, for retrieval */ static XImage *tile_image = 0; /* --- 219,224 ---- *************** *** 270,277 **** if (tile_image == 0) return; /* no tiles */ ! height = tile_height * ((tile_count+tiles_per_line-1)/tiles_per_line); ! width = tile_width * tiles_per_line; tile_pixmap = XCreatePixmap(dpy, XtWindow(toplevel), width, --- 271,278 ---- if (tile_image == 0) return; /* no tiles */ ! height = tile_height * tiles_per_col; ! width = tile_width * tiles_per_row; tile_pixmap = XCreatePixmap(dpy, XtWindow(toplevel), width, *************** *** 416,426 **** goto tiledone; } ! if (tile_image->height%total_tiles_used != 0) { char buf[BUFSIZ]; Sprintf(buf, ! "%s is not a multiple of %d (the number of tiles) pixels high", ! appResources.tile_file, total_tiles_used); X11_raw_print(buf); XDestroyImage(tile_image); tile_image = 0; --- 417,431 ---- goto tiledone; } ! if (tile_image->height%tiles_per_col != 0 || ! tile_image->width%tiles_per_row != 0) { char buf[BUFSIZ]; Sprintf(buf, ! "%s appears to have a non-integer tile size.\n" ! "Its size (%dx%d) should be a multiple of %dx%d", ! appResources.tile_file, ! tile_image->width,tile_image->height, ! tiles_per_row,tiles_per_col); X11_raw_print(buf); XDestroyImage(tile_image); tile_image = 0; *************** *** 430,447 **** /* infer tile dimensions from image size */ tile_count=total_tiles_used; ! tile_width=tile_image->width; ! tile_height=tile_image->height/tile_count; ! /* ! * Only ever one tile per line in XPM mode. ! * To change this would require either changing the XPM data file ! * (in which case how do we know how many tiles per line?), or ! * some fancy reading algorithm which will convert on the fly ! * without triggering the X bug which causes the problem in the ! * first place. ! * For now, just be careful that image height does not exceed 32767. ! */ ! tiles_per_line=1; } #else /* any less than 16 colours makes tiles useless */ --- 435,442 ---- /* infer tile dimensions from image size */ tile_count=total_tiles_used; ! tile_width=tile_image->width/tiles_per_row; ! tile_height=tile_image->height/tiles_per_col; } #else /* any less than 16 colours makes tiles useless */ *************** *** 545,553 **** * so that we avoid dimensions larger than 32767 which trigger a * bug in XPutImage (at least on Solaris 2.5.1). */ ! tiles_per_line = 32767/tile_width; ! image_width = tile_width * tiles_per_line; ! image_height = tile_height * ((tile_count+tiles_per_line-1)/tiles_per_line); /* calculate bitmap_pad */ if (ddepth > 16) --- 540,547 ---- * so that we avoid dimensions larger than 32767 which trigger a * bug in XPutImage (at least on Solaris 2.5.1). */ ! image_width = tile_width * tiles_per_row; ! image_height = tile_height * tiles_per_col; /* calculate bitmap_pad */ if (ddepth > 16) *************** *** 581,600 **** for (x = 0; x < header.tile_width; x++, tb++) { XPutPixel(tile_image, ! (i % tiles_per_line) * tile_width + 2*x, ! (i / tiles_per_line) * tile_height + 2*y, colors[*tb].pixel); XPutPixel(tile_image, ! (i % tiles_per_line) * tile_width + 2*x, ! (i / tiles_per_line) * tile_height + 2*y+1, colors[*tb].pixel); XPutPixel(tile_image, ! (i % tiles_per_line) * tile_width + 2*x+1, ! (i / tiles_per_line) * tile_height + 2*y, colors[*tb].pixel); XPutPixel(tile_image, ! (i % tiles_per_line) * tile_width + 2*x+1, ! (i / tiles_per_line) * tile_height + 2*y+1, colors[*tb].pixel); } } --- 575,594 ---- for (x = 0; x < header.tile_width; x++, tb++) { XPutPixel(tile_image, ! (i % tiles_per_row) * tile_width + 2*x, ! (i / tiles_per_row) * tile_height + 2*y, colors[*tb].pixel); XPutPixel(tile_image, ! (i % tiles_per_row) * tile_width + 2*x, ! (i / tiles_per_row) * tile_height + 2*y+1, colors[*tb].pixel); XPutPixel(tile_image, ! (i % tiles_per_row) * tile_width + 2*x+1, ! (i / tiles_per_row) * tile_height + 2*y, colors[*tb].pixel); XPutPixel(tile_image, ! (i % tiles_per_row) * tile_width + 2*x+1, ! (i / tiles_per_row) * tile_height + 2*y+1, colors[*tb].pixel); } } *************** *** 605,612 **** for (y = 0; y < header.tile_height; y++) for (x = 0; x < header.tile_width; x++, tb++) XPutPixel(tile_image, ! (i % tiles_per_line) * tile_width + x, ! (i / tiles_per_line) * tile_height + y, colors[*tb].pixel); } } --- 599,606 ---- for (y = 0; y < header.tile_height; y++) for (x = 0; x < header.tile_width; x++, tb++) XPutPixel(tile_image, ! (i % tiles_per_row) * tile_width + x, ! (i / tiles_per_row) * tile_height + y, colors[*tb].pixel); } } *************** *** 1307,1314 **** XCopyArea(dpy, tile_pixmap, XtWindow(wp->w), tile_map->black_gc, /* no grapics_expose */ ! (tile % tiles_per_line) * map_info->square_width, ! (tile / tiles_per_line) * map_info->square_height, tile_width, tile_height, dest_x,dest_y); if (glyph_is_pet(glyph) --- 1301,1308 ---- XCopyArea(dpy, tile_pixmap, XtWindow(wp->w), tile_map->black_gc, /* no grapics_expose */ ! (tile % tiles_per_row) * map_info->square_width, ! (tile / tiles_per_row) * map_info->square_height, tile_width, tile_height, dest_x,dest_y); if (glyph_is_pet(glyph) *** win/gtk/gtkmap.c.orig Mon Jan 31 14:53:08 2000 --- win/gtk/gtkmap.c Fri Jan 28 19:25:41 2000 *************** *** 150,157 **** static int map_visual = 1; #endif static char *NH_TILE_FILE; - static int NH_TILE_PER_COL; static int NH_TILE_3D_WIDTH; static int NH_TILE_3D_HEIGHT; static int NH_TILE_3D_OFSET; --- 150,160 ---- static int map_visual = 1; #endif + /* from tile.c */ + extern int tiles_per_row; + extern int tiles_per_col; + static char *NH_TILE_FILE; static int NH_TILE_3D_WIDTH; static int NH_TILE_3D_HEIGHT; static int NH_TILE_3D_OFSET; *************** *** 168,175 **** static int NH_MAP_MAX_WIDTH; static int NH_MAP_MAX_HEIGHT; ! #define FLOOR_SRC_X (((345 + 394 + 12) % NH_TILE_PER_COL) * NH_TILE_WIDTH) ! #define FLOOR_SRC_Y (((345 + 394 + 12) / NH_TILE_PER_COL) * NH_TILE_HEIGHT) #ifdef RADAR #define NH_RADAR_UNIT 4 --- 171,178 ---- static int NH_MAP_MAX_WIDTH; static int NH_MAP_MAX_HEIGHT; ! #define FLOOR_SRC_X (((345 + 394 + 12) % tiles_per_row) * NH_TILE_WIDTH) ! #define FLOOR_SRC_Y (((345 + 394 + 12) / tiles_per_row) * NH_TILE_HEIGHT) #ifdef RADAR #define NH_RADAR_UNIT 4 *************** *** 255,261 **** gdk_window_get_size((GdkWindow *)tile_pixmap, &NH_TILEMAP_WIDTH, &NH_TILEMAP_HEIGHT); - NH_TILE_PER_COL = NH_TILEMAP_WIDTH / Tile->unit_width; tile_image = gdk_image_get( (GdkWindow *)tile_pixmap, --- 258,263 ---- *************** *** 590,596 **** gdk_window_get_size((GdkWindow *)tile_pixmap, &NH_TILEMAP_WIDTH, &NH_TILEMAP_HEIGHT); - NH_TILE_PER_COL = NH_TILEMAP_WIDTH / Tile->unit_width; tile_image = gdk_image_get( (GdkWindow *)tile_pixmap, --- 592,597 ---- *************** *** 867,877 **** int src_x, src_y; int bgsrc_x, bgsrc_y; ! src_x = (tile % NH_TILE_PER_COL) * c_width; ! src_y = (tile / NH_TILE_PER_COL) * c_height; ! bgsrc_x = (bgtile % NH_TILE_PER_COL) * c_width; ! bgsrc_y = (bgtile / NH_TILE_PER_COL) * c_height; if(!Tile->transparent){ if(flag == False) --- 868,878 ---- int src_x, src_y; int bgsrc_x, bgsrc_y; ! src_x = (tile % tiles_per_row) * c_width; ! src_y = (tile / tiles_per_row) * c_height; ! bgsrc_x = (bgtile % tiles_per_row) * c_width; ! bgsrc_y = (bgtile / tiles_per_row) * c_height; if(!Tile->transparent){ if(flag == False) *** win/share/tilemap.c.orig Mon Jan 31 14:53:08 2000 --- win/share/tilemap.c Fri Jan 28 19:25:41 2000 *************** *** 308,332 **** #else /* TILETEXT */ ! #define TILE_FILE "tile.c" #ifdef AMIGA # define SOURCE_TEMPLATE "NH:src/%s" #else # ifdef MAC # define SOURCE_TEMPLATE ":src:%s" # else # define SOURCE_TEMPLATE "../src/%s" # endif #endif short tilemap[MAX_GLYPH]; int lastmontile, lastobjtile, lastothtile; /* Number of tiles for invisible monsters */ #define NUM_INVIS_TILES 1 /* * set up array to map glyph numbers to tile numbers * * assumes tiles are numbered sequentially through monsters/objects/other, --- 308,426 ---- #else /* TILETEXT */ ! #define TILE_FILE_H "tile.h" ! #define TILE_FILE_C "tile.c" #ifdef AMIGA + # define INCLUDE_TEMPLATE "NH:include/t.%s" # define SOURCE_TEMPLATE "NH:src/%s" + # define SHARE_IN_TEMPLATE "NH:share/%s" #else # ifdef MAC + # define INCLUDE_TEMPLATE ":include:%s" # define SOURCE_TEMPLATE ":src:%s" + # define SHARE_IN_TEMPLATE ":share:%s" # else + # ifdef OS2 + # define INCLUDE_TEMPLATE "..\\include\\%s" + # define SOURCE_TEMPLATE "..\\src\\%s" + # define SHARE_IN_TEMPLATE "..\\win\\share\\%s" + # else + # define INCLUDE_TEMPLATE "../include/%s" # define SOURCE_TEMPLATE "../src/%s" + # define SHARE_IN_TEMPLATE "../win/share/%s" + # endif # endif #endif short tilemap[MAX_GLYPH]; int lastmontile, lastobjtile, lastothtile; + static char in_line[256]; + /* Number of tiles for invisible monsters */ #define NUM_INVIS_TILES 1 /* + * ALI + * + * Compute the value of ceil(sqrt(c)) using only integer arithmetic. + * + * Newton-Raphson gives us the following algorithm for solving sqrt(c): + * + * a[n]^2+c + * a[n+1] = -------- + * 2*a[n] + * + * It would be tempting to use a[n+1] = (a[n]^2+c+2*a[n]-1) div 2*a[n] + * to solve for ceil(sqrt(c)) but this does not converge correctly. + * Instead we solve floor(sqrt(c)) first and then adjust as necessary. + * + * The proposed algorithm to solve floor(sqrt(c)): + * + * a[n+1] = a[n]^2+c div 2*a[n] + * + * If we define the deviation of approximation n as follows: + * + * e[n] = a[n] - sqrt(c) + * + * Then it follows that: + * + * e[n]^2 + * e[n+1] = --------------- + * 2(e[n]+sqrt(c)) + * + * The sequence will converge to the solution if: + * + * | e[n+1] | < | e[n] | + * + * which becomes: + * + * | e[n]^2 | + * | --------------- | < | e[n] | + * | 2(e[n]+sqrt(c)) | + * + * This splits into three cases: + * + * If e[n] > 0 * If 0 > e[n] >= -sqrt(c) * If e[n] < -sqrt(c) + * * * + * Converges iff: * Converges iff: * Converges iff: + * * 2 * + * e[n] > -2*sqrt(c) * e[n] > - - sqrt(c) * e[n] > -2*sqrt(c) + * * 3 * + * * sqrt(c) * + * True for all cases. * True iff a[n] > ------- * True iff 0 > a[n] > -sqrt(c) + * * 3 * + * + * Case 3 represents failure, but this can be avoided by choosing a positive + * initial value. In both case 1 and case 2, e[n+1] is positive regardless + * of the sign of e[n]. It therefore follows that even if an initial value + * between 0 and sqrt(c)/3 is chosen, we will only diverge for one iteration. + * + * Therefore the algorithm will converge correctly as long as we start + * with a positve inital value (it will converge to the negative root if + * we start with a negative initial value and fail if we start with zero). + * + * We choose an initial value designed to be close to the solution we expect + * for typical values of c. This also makes it unlikely that we will cause + * a divergence. If we do, it will only take a few more iterations. + */ + + int ceil_sqrt(c) + int c; + { + int a=c/36,la; /* Approximation and last approximation */ + /* Compute floor(sqrt(c)) */ + do + { + la=a; + a=(a*a+c)/(2*a); + } while (a!=la); + /* Adjust for ceil(sqrt(c)) */ + return a*a==c?a:a+1; + } + + /* * set up array to map glyph numbers to tile numbers * * assumes tiles are numbered sequentially through monsters/objects/other, *************** *** 507,512 **** --- 601,609 ---- } fprintf(ofp, "\nint total_tiles_used = %d;\n", start); + i = ceil_sqrt(start); + fprintf(ofp, "int tiles_per_row = %d;\n", i); + fprintf(ofp, "int tiles_per_col = %d;\n", (start + i - 1) / i); lastothtile = start - 1; } *************** *** 514,527 **** { register int i; char filename[30]; ! FILE *ofp; init_tilemap(); /* * create the source file, "tile.c" */ ! Sprintf(filename, SOURCE_TEMPLATE, TILE_FILE); if (!(ofp = fopen(filename, "w"))) { perror(filename); exit(EXIT_FAILURE); --- 611,624 ---- { register int i; char filename[30]; ! FILE *ifp,*ofp; init_tilemap(); /* * create the source file, "tile.c" */ ! Sprintf(filename, SOURCE_TEMPLATE, TILE_FILE_C); if (!(ofp = fopen(filename, "w"))) { perror(filename); exit(EXIT_FAILURE); *************** *** 544,549 **** --- 641,674 ---- fprintf(ofp,"\n/*tile.c*/\n"); fclose(ofp); + + /* + * create the include file, "tile.h" + */ + Sprintf(filename, SHARE_IN_TEMPLATE, TILE_FILE_H); + if (!(ifp = fopen(filename, "r"))) { + perror(filename); + exit(EXIT_FAILURE); + } + Sprintf(filename, INCLUDE_TEMPLATE, TILE_FILE_H); + if (!(ofp = fopen(filename, "w"))) { + perror(filename); + exit(EXIT_FAILURE); + } + fprintf(ofp,"/* This file is automatically generated. Do not edit. */\n"); + + fprintf(ofp,"\n#define TOTAL_TILES_USED %d\n", lastothtile + 1); + i = ceil_sqrt(lastothtile + 1); + fprintf(ofp,"#define TILES_PER_ROW %d\n", i); + fprintf(ofp,"#define TILES_PER_COL %d\n\n", (lastothtile + i) / i); + + while (fgets(in_line, sizeof in_line, ifp) != 0) + (void) fputs(in_line, ofp); + + fprintf(ofp,"\n/*tile.h*/\n"); + + fclose(ofp); + exit(EXIT_SUCCESS); /*NOTREACHED*/ return 0; *** sys/unix/Makefile.utl.orig Mon Jan 31 14:53:08 2000 --- sys/unix/Makefile.utl Tue Feb 1 16:45:06 2000 *************** *** 273,281 **** $(CC) $(CFLAGS) $(LFLAGS) -o tilemap ../win/share/tilemap.c ../src/tile.c: tilemap ./tilemap - ../include/tile.h: ../win/share/tile.h - cp ../win/share/tile.h ../include/tile.h tiletext.o: ../win/share/tiletext.c ../include/config.h ../include/tile.h $(CC) $(CFLAGS) -c ../win/share/tiletext.c tiletxt.o: ../win/share/tilemap.c ../include/hack.h --- 273,281 ---- $(CC) $(CFLAGS) $(LFLAGS) -o tilemap ../win/share/tilemap.c ../src/tile.c: tilemap ./tilemap + ../include/tile.h: ../win/share/tile.h tilemap + ./tilemap tiletext.o: ../win/share/tiletext.c ../include/config.h ../include/tile.h $(CC) $(CFLAGS) -c ../win/share/tiletext.c tiletxt.o: ../win/share/tilemap.c ../include/hack.h