X-Git-Url: https://git.artsoft.org/?a=blobdiff_plain;f=src%2Ftools.c;h=0271abfc43d83eb615b99fe8663df7cd83e0a5d5;hb=00f1c42e2779f15ae0e68dc820292141bb2cea2f;hp=1e7fef67ff45883163b177bdc6ad061889f50df6;hpb=c07e4d51f30c46731bf28c42954dc7726457984e;p=rocksndiamonds.git diff --git a/src/tools.c b/src/tools.c index 1e7fef67..0271abfc 100644 --- a/src/tools.c +++ b/src/tools.c @@ -1416,39 +1416,42 @@ void SetBorderElement(void) } } -void FloodFillLevelExt(int from_x, int from_y, int fill_element, +void FloodFillLevelExt(int start_x, int start_y, int fill_element, int max_array_fieldx, int max_array_fieldy, short field[max_array_fieldx][max_array_fieldy], int max_fieldx, int max_fieldy) { - int i,x,y; - int old_element; - static int check[4][2] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } }; - static int safety = 0; + static struct XY stack_buffer[MAX_LEV_FIELDX * MAX_LEV_FIELDY]; + static struct XY check[4] = { { -1, 0 }, { 0, -1 }, { 1, 0 }, { 0, 1 } }; + int old_element = field[start_x][start_y]; + int stack_pos = 0; - // check if starting field still has the desired content - if (field[from_x][from_y] == fill_element) + // do nothing if start field already has the desired content + if (old_element == fill_element) return; - safety++; + stack_buffer[stack_pos++] = (struct XY){ start_x, start_y }; - if (safety > max_fieldx * max_fieldy) - Fail("Something went wrong in 'FloodFill()'. Please debug."); + while (stack_pos > 0) + { + struct XY current = stack_buffer[--stack_pos]; + int i; - old_element = field[from_x][from_y]; - field[from_x][from_y] = fill_element; + field[current.x][current.y] = fill_element; - for (i = 0; i < 4; i++) - { - x = from_x + check[i][0]; - y = from_y + check[i][1]; + for (i = 0; i < 4; i++) + { + int x = current.x + check[i].x; + int y = current.y + check[i].y; - if (IN_FIELD(x, y, max_fieldx, max_fieldy) && field[x][y] == old_element) - FloodFillLevelExt(x, y, fill_element, max_array_fieldx, max_array_fieldy, - field, max_fieldx, max_fieldy); - } + // check for stack buffer overflow (should not happen) + if (stack_pos >= MAX_LEV_FIELDX * MAX_LEV_FIELDY) + Fail("Stack buffer overflow in 'FloodFillLevelExt()'. Please debug."); - safety--; + if (IN_FIELD(x, y, max_fieldx, max_fieldy) && field[x][y] == old_element) + stack_buffer[stack_pos++] = (struct XY){ x, y }; + } + } } void FloodFillLevel(int from_x, int from_y, int fill_element, @@ -1478,6 +1481,25 @@ int getGraphicAnimationFrame(int graphic, int sync_frame) sync_frame); } +int getGraphicAnimationFrameXY(int graphic, int lx, int ly) +{ + if (graphic_info[graphic].anim_mode & ANIM_TILED) + { + struct GraphicInfo *g = &graphic_info[graphic]; + int xsize = MAX(1, g->anim_frames_per_line); + int ysize = MAX(1, g->anim_frames / xsize); + int xoffset = g->anim_start_frame % xsize; + int yoffset = g->anim_start_frame % ysize; + int x = (lx + xoffset + xsize) % xsize; + int y = (ly + yoffset + ysize) % ysize; + int sync_frame = y * xsize + x; + + return sync_frame % g->anim_frames; + } + + return getGraphicAnimationFrame(graphic, GfxFrame[lx][ly]); +} + void getGraphicSourceBitmap(int graphic, int tilesize, Bitmap **bitmap) { struct GraphicInfo *g = &graphic_info[graphic]; @@ -1970,13 +1992,13 @@ void DrawScreenElementExt(int x, int y, int dx, int dy, int element, SetRandomAnimationValue(lx, ly); graphic = el_act_dir2img(element, GfxAction[lx][ly], GfxDir[lx][ly]); - frame = getGraphicAnimationFrame(graphic, GfxFrame[lx][ly]); + frame = getGraphicAnimationFrameXY(graphic, lx, ly); // do not use double (EM style) movement graphic when not moving if (graphic_info[graphic].double_movement && !dx && !dy) { graphic = el_act_dir2img(element, ACTION_DEFAULT, GfxDir[lx][ly]); - frame = getGraphicAnimationFrame(graphic, GfxFrame[lx][ly]); + frame = getGraphicAnimationFrameXY(graphic, lx, ly); } if (game.use_masked_elements && (dx || dy)) @@ -1985,7 +2007,7 @@ void DrawScreenElementExt(int x, int y, int dx, int dy, int element, else // border element { graphic = el2img(element); - frame = getGraphicAnimationFrame(graphic, -1); + frame = getGraphicAnimationFrameXY(graphic, lx, ly); } if (element == EL_EXPANDABLE_WALL) @@ -2102,7 +2124,7 @@ static void DrawLevelFieldCrumbledInnerCorners(int x, int y, int dx, int dy, if (game.use_masked_elements) { int graphic0 = el2img(EL_EMPTY); - int frame0 = getGraphicAnimationFrame(graphic0, GfxFrame[x][y]); + int frame0 = getGraphicAnimationFrameXY(graphic0, x, y); Bitmap *src_bitmap0; int src_x0, src_y0; @@ -2140,7 +2162,7 @@ static void DrawLevelFieldCrumbledBorders(int x, int y, int graphic, int frame, // only needed when using masked elements int graphic0 = el2img(EL_EMPTY); - int frame0 = getGraphicAnimationFrame(graphic0, GfxFrame[x][y]); + int frame0 = getGraphicAnimationFrameXY(graphic0, x, y); Bitmap *src_bitmap0; int src_x0, src_y0; @@ -3528,8 +3550,8 @@ static void DrawPreviewLevelExt(boolean restart) DrawPreviewLevelInfo(MICROLABEL_LEVEL_AUTHOR); // initialize delay counters - DelayReached(&scroll_delay, 0); - DelayReached(&label_delay, 0); + ResetDelayCounter(&scroll_delay); + ResetDelayCounter(&label_delay); if (leveldir_current->name) { @@ -3672,7 +3694,7 @@ void DrawPreviewPlayers(void) { int element = level.field[x][y]; - if (ELEM_IS_PLAYER(element)) + if (IS_PLAYER_ELEMENT(element)) { int player_nr = GET_PLAYER_NR(element); @@ -3837,10 +3859,10 @@ void ClearNetworkPlayers(void) } static void DrawGraphicAnimationExt(DrawBuffer *dst_bitmap, int x, int y, - int graphic, int sync_frame, + int graphic, int lx, int ly, int mask_mode) { - int frame = getGraphicAnimationFrame(graphic, sync_frame); + int frame = getGraphicAnimationFrameXY(graphic, lx, ly); if (mask_mode == USE_MASKING) DrawGraphicThruMaskExt(dst_bitmap, x, y, graphic, frame); @@ -3878,7 +3900,7 @@ static void DrawGraphicAnimation(int x, int y, int graphic) } DrawGraphicAnimationExt(drawto_field, FX + x * TILEX_VAR, FY + y * TILEY_VAR, - graphic, GfxFrame[lx][ly], mask_mode); + graphic, lx, ly, mask_mode); MarkTileDirty(x, y); } @@ -3902,7 +3924,7 @@ void DrawFixedGraphicAnimation(int x, int y, int graphic) } DrawGraphicAnimationExt(drawto_field, FX + x * TILEX, FY + y * TILEY, - graphic, GfxFrame[lx][ly], mask_mode); + graphic, lx, ly, mask_mode); MarkTileDirty(x, y); } @@ -3929,6 +3951,9 @@ void DrawLevelGraphicAnimationIfNeeded(int x, int y, int graphic) if (!IS_NEW_FRAME(GfxFrame[x][y], graphic)) return; + if (ANIM_MODE(graphic) & ANIM_TILED) + return; + DrawGraphicAnimation(sx, sy, graphic); #if 1 @@ -4274,7 +4299,7 @@ static void DrawPlayerExt(struct PlayerInfo *player, int drawing_stage) if (IS_ACTIVE_BOMB(element)) { int graphic = el2img(element); - int frame = getGraphicAnimationFrame(graphic, GfxFrame[jx][jy]); + int frame = getGraphicAnimationFrameXY(graphic, jx, jy); if (game.emulation == EMU_SUPAPLEX) DrawGraphic(sx, sy, IMG_SP_DISK_RED, frame); @@ -9901,3 +9926,196 @@ void ChangeViewportPropertiesIfNeeded(void) InitGraphicInfo_EM(); } } + + +// ============================================================================ +// tests +// ============================================================================ + +#if defined(PLATFORM_WIN32) +/* FILETIME of Jan 1 1970 00:00:00. */ +static const unsigned __int64 epoch = ((unsigned __int64) 116444736000000000ULL); + +/* + * timezone information is stored outside the kernel so tzp isn't used anymore. + * + * Note: this function is not for Win32 high precision timing purpose. See + * elapsed_time(). + */ +int gettimeofday_windows(struct timeval * tp, struct timezone * tzp) +{ + FILETIME file_time; + SYSTEMTIME system_time; + ULARGE_INTEGER ularge; + + GetSystemTime(&system_time); + SystemTimeToFileTime(&system_time, &file_time); + ularge.LowPart = file_time.dwLowDateTime; + ularge.HighPart = file_time.dwHighDateTime; + + tp->tv_sec = (long) ((ularge.QuadPart - epoch) / 10000000L); + tp->tv_usec = (long) (system_time.wMilliseconds * 1000); + + return 0; +} +#endif + +static char *test_init_uuid_random_function_simple(void) +{ + static char seed_text[100]; + unsigned int seed = InitSimpleRandom(NEW_RANDOMIZE); + + sprintf(seed_text, "%d", seed); + + return seed_text; +} + +static char *test_init_uuid_random_function_better(void) +{ + static char seed_text[100]; + struct timeval current_time; + + gettimeofday(¤t_time, NULL); + + prng_seed_bytes(¤t_time, sizeof(current_time)); + + sprintf(seed_text, "%ld.%ld", + (long)current_time.tv_sec, + (long)current_time.tv_usec); + + return seed_text; +} + +#if defined(PLATFORM_WIN32) +static char *test_init_uuid_random_function_better_windows(void) +{ + static char seed_text[100]; + struct timeval current_time; + + gettimeofday_windows(¤t_time, NULL); + + prng_seed_bytes(¤t_time, sizeof(current_time)); + + sprintf(seed_text, "%ld.%ld", + (long)current_time.tv_sec, + (long)current_time.tv_usec); + + return seed_text; +} +#endif + +static unsigned int test_uuid_random_function_simple(int max) +{ + return GetSimpleRandom(max); +} + +static unsigned int test_uuid_random_function_better(int max) +{ + return (max > 0 ? prng_get_uint() % max : 0); +} + +#if defined(PLATFORM_WIN32) +#define NUM_UUID_TESTS 3 +#else +#define NUM_UUID_TESTS 2 +#endif + +static void TestGeneratingUUIDs_RunTest(int nr, int always_seed, int num_uuids) +{ + struct hashtable *hash_seeds = + create_hashtable(16, 0.75, get_hash_from_key, hash_keys_are_equal); + struct hashtable *hash_uuids = + create_hashtable(16, 0.75, get_hash_from_key, hash_keys_are_equal); + static char message[100]; + int i; + + char *random_name = (nr == 0 ? "simple" : "better"); + char *random_type = (always_seed ? "always" : "only once"); + char *(*init_random_function)(void) = + (nr == 0 ? + test_init_uuid_random_function_simple : + test_init_uuid_random_function_better); + unsigned int (*random_function)(int) = + (nr == 0 ? + test_uuid_random_function_simple : + test_uuid_random_function_better); + int xpos = 40; + +#if defined(PLATFORM_WIN32) + if (nr == 2) + { + random_name = "windows"; + init_random_function = test_init_uuid_random_function_better_windows; + } +#endif + + ClearField(); + + DrawTextF(xpos, 40, FC_GREEN, "Test: Generating UUIDs"); + DrawTextF(xpos, 80, FC_YELLOW, "Test %d.%d:", nr + 1, always_seed + 1); + + DrawTextF(xpos, 100, FC_YELLOW, "Random Generator Name: %s", random_name); + DrawTextF(xpos, 120, FC_YELLOW, "Seeding Random Generator: %s", random_type); + DrawTextF(xpos, 140, FC_YELLOW, "Number of UUIDs generated: %d", num_uuids); + + DrawTextF(xpos, 180, FC_GREEN, "Please wait ..."); + + BackToFront(); + + // always initialize random number generator at least once + init_random_function(); + + unsigned int time_start = SDL_GetTicks(); + + for (i = 0; i < num_uuids; i++) + { + if (always_seed) + { + char *seed = getStringCopy(init_random_function()); + + hashtable_remove(hash_seeds, seed); + hashtable_insert(hash_seeds, seed, "1"); + } + + char *uuid = getStringCopy(getUUIDExt(random_function)); + + hashtable_remove(hash_uuids, uuid); + hashtable_insert(hash_uuids, uuid, "1"); + } + + int num_unique_seeds = hashtable_count(hash_seeds); + int num_unique_uuids = hashtable_count(hash_uuids); + + unsigned int time_needed = SDL_GetTicks() - time_start; + + DrawTextF(xpos, 220, FC_YELLOW, "Time needed: %d ms", time_needed); + + DrawTextF(xpos, 240, FC_YELLOW, "Number of unique UUIDs: %d", num_unique_uuids); + + if (always_seed) + DrawTextF(xpos, 260, FC_YELLOW, "Number of unique seeds: %d", num_unique_seeds); + + if (nr == NUM_UUID_TESTS - 1 && always_seed) + DrawTextF(xpos, 300, FC_GREEN, "All tests done!"); + else + DrawTextF(xpos, 300, FC_GREEN, "Confirm dialog for next test ..."); + + sprintf(message, "Test %d.%d finished!", nr + 1, always_seed + 1); + + Request(message, REQ_CONFIRM); + + hashtable_destroy(hash_seeds, 0); + hashtable_destroy(hash_uuids, 0); +} + +void TestGeneratingUUIDs(void) +{ + int num_uuids = 1000000; + int i, j; + + for (i = 0; i < NUM_UUID_TESTS; i++) + for (j = 0; j < 2; j++) + TestGeneratingUUIDs_RunTest(i, j, num_uuids); + + CloseAllAndExit(0); +}