Rockbox

  • Status Closed
  • Percent Complete
    100%
  • Task Type Patches
  • Category Games
  • Assigned To No-one
  • Operating System All players
  • Severity Low
  • Priority Very Low
  • Reported Version Daily build (which?)
  • Due in Version Undecided
  • Due Date Undecided
  • Votes
  • Private
Attached to Project: Rockbox
Opened by wpyh - 2008-07-13
Last edited by jdgordon - 2008-07-15

FS#9191 - Revamp of maze plugin code (apps/plugins/maze.c)

I’ve revamped the code in apps/plugins/maze.c while fixing the bug in  FS#9184 . Here are the main changes:

1. Whitespace changes.

2. Code cleanups.

3. Comments for non-trivial code blocks.

4. Make all functions static.

5. Reorder and regroup several functions.

6. Use border-detection macros instead of border property bits, use 8 bit entities for each cell.

7. Only solve the maze the first time maze_solve() is called.

8. Add and use maze.show_path to control whether the solution is displayed.

9. Modify the path bits only in maze_solve().

10. Modify the algorithm in maze_solve() to make it clearer.

11. Link together the solution instead of showing discrete blocks.

12. Rewrite maze_pick_random_neighbour_cell_with_walls(), and remove coord_stack_count() and coord_stack_get().

13. Rewrite the coordinate stack operations, use arrays of x and y coordinates.

14. Remove bug workaround with rb→yield() when quitting.

This fixes  FS#9184 , so if this patch is accepted, that task can also be closed.

Closed by  jdgordon
2008-07-15 13:49
Reason for closing:  Accepted
vmh commented on 2008-07-14 16:17

Your patch fixes  FS#9184  on my E200. What was the cause for the crash?

wpyh commented on 2008-07-14 18:17

Well, I’m not really sure how it works, but the crash was caused by some stack overflow.

The quick fix was to change:

struct coord_stack
{

  int data[MAZE_WIDTH*MAZE_HEIGHT];
  int stp;

};

to

struct coord_stack
{

  unsigned short data[MAZE_WIDTH*MAZE_HEIGHT];
  int stp;

};

But as you can see,
1. That “fix” was too simplistic and didn’t take into account other factors.
2. The data (array) inside struct coord_stack and struct_maze are similar only because of a coincidence.
3. I got itchy and started making changes here and there.

I’ve played with it and didn’t find any problems. Solving the maze takes some time, and I hope that can be optimized, but let’s save it for later. I’m hoping this patch gets accepted first :)

vmh commented on 2008-07-14 19:50

Thank you for the explanation. I think I see the problem.
The parameters x and y for push and pop are integers, but only the lower 8 bits from x and y are used.
When x or y exceeds 255 or negative, the value on the stack will be wrong.
It’s funny that if you change the stack to ‘unsigned short’ will work.
I would say the correct fix for the old code would be to leave the stack as integer but change the parameters x and y for push and pop to unsigned short.

I see in your new version the parameters for the data to push and pop from stack are still integer while the stack is expecting unsigned short.
I would change it if I were you.

vmh commented on 2008-07-14 20:19

Here is a patch for the original maze code. I cleared the higher 8 bits from y which can corrupt the stack and it works on my player.

wpyh commented on 2008-07-15 03:54

That is even stranger than the original problem. coord_stack_push is called with x and y coordinates, which can never be negative or more than 255. Actually the largest maze we have is 32×24 (and this will be the largest for quite a long time).

Therefore I think the problem lies with some code that calls coord_stack_push with invalid coordinates. By clearing the higher bits from y, we are effectively hiding the problem. Please track down the caller :)

Meanwhile, my patch changes the function to:

static void coord_stack_push(struct coord_stack* stack, int x, int y)
{

  stack->x[stack->stp] = x;
  stack->y[stack->stp] = y;
  stack->stp++;

}

The stack is implemented by two uint8_t arrays, which means that x and y are cast to uint8_t. This means that if a caller calls coord_stack_push with the wrong values, it will still behave erratically. However, we cannot solve the problem inside this function. We have to track down the caller.

Since I’ve rewritten / revamped most of the functions, the problem may have been fixed by me, or hidden somewhere. I hope that you will test my patch, and see whether it works correctly, especially for showing the path (the solution, see maze_draw()) – I’ve linked the cells in the path, as opposed to just highlighting every cell in the path.

wpyh commented on 2008-07-15 05:04

This is a newer version.

15. Moved “#include pluginlib_actions.h” and plugin_contexts into one #ifdef.

Loading...

Available keyboard shortcuts

Tasklist

Task Details

Task Editing