Recent

Author Topic: [solved] weird segfault [--> stack overflow]  (Read 2566 times)

big_M

  • New Member
  • *
  • Posts: 40
Re: weird segfault
« Reply #15 on: October 12, 2021, 12:42:22 pm »
Okey, so I tried to compile it with the TAILREC optimization. For this I quickly merged the two procedures into one. The code looks like this now:
Code: Pascal  [Select][+][-]
  1. procedure FillFloodMaps(x,y,dist:integer; fillHeight:single);
  2. var DEM_NoDataValue,DEM_Height: single;
  3.     run: boolean;
  4. begin
  5.   run:=false;
  6.   if FlowMap[x,y] >= dist then
  7.     if FloodHeightMap[x,y] < fillHeight then
  8.     begin
  9.       DEM.GetPixel(x,y,single(DEM_Height));
  10.       DEM.GetNoDataValue(single(DEM_NoDataValue));
  11.       if (DEM_Height<>DEM_NoDataValue) AND (DEM_Height<fillHeight) then
  12.       begin
  13.         FloodHeightMap[x,y]:=fillHeight;
  14.         FloodDepthMap[x,y]:=fillHeight-DEM_Height;
  15.         run:=true;
  16.         //FillFloodMaps_Crawler(x,y,dist,fillHeight); {removed}
  17.       end;
  18.     end;
  19.   if run then
  20.   begin
  21.     if (x+1<=Flood.Width-1)                           then FillFloodMaps(x+1,y,  dist,fillHeight);
  22.     if (x+1<=Flood.Width-1) AND (y+1<=Flood.Height-1) then FillFloodMaps(x+1,y+1,dist,fillHeight);
  23.     if                          (y+1<=Flood.Height-1) then FillFloodMaps(x,y+1,  dist,fillHeight);
  24.     if (x-1>=0)             AND (y+1<=Flood.Height-1) then FillFloodMaps(x-1,y+1,dist,fillHeight);
  25.     if (x-1>=0)                                       then FillFloodMaps(x-1,y,  dist,fillHeight);
  26.     if (x-1>=0)             AND (y-1>=0)              then FillFloodMaps(x-1,y-1,dist,fillHeight);
  27.     if                          (y-1>=0)              then FillFloodMaps(x,y-1,  dist,fillHeight);
  28.     if (x+1<=Flood.Width-1) AND (y-1>=0)              then FillFloodMaps(x+1,y-1,dist,fillHeight);
  29.   end;
  30. end;                    

Unfortunately the optimization doesn't work. But now I'm wondering if this case really is a tail recursion? I'm not too sure about the definition of a tail recursion, but in my case I have multiple lines which run the procedure, so if it is run the first time (line 21) there is still code behind it (even though they all just run the procedure).

Warfley

  • Hero Member
  • *****
  • Posts: 596
Re: weird segfault
« Reply #16 on: October 12, 2021, 04:21:04 pm »
I've been wrong in my previous post, this is not a tail recursion, as these if statements are not mutually exclusive (i.e. else if).

You could change this by having a fixed order in which you traverse, e.g. zig zag (i.e. first 0,0 then 1,0 then 0,1 then 2,0 then 1,1 then 0,2 then 3,0 then 2,1 then 1,2 then 0,3 and so on)
This covers every pixel and only requires one recursive call in the end making it a tail recursion

big_M

  • New Member
  • *
  • Posts: 40
Re: weird segfault
« Reply #17 on: October 12, 2021, 05:33:06 pm »
Okey, thanks :) Then I know I haven't done this for nothing, because I have rewritten it now without recursion.

@winni: Thanks for your example. I must say I didn't really understand it, so I just gave it a try myself. I guess the result is something similar though in the end. So far it seems to run fine.

I'll post the code just in case someone would find it usefull:
Code: Pascal  [Select][+][-]
  1. procedure FillFloodMaps(x,y,dist:integer; fillHeight:single);
  2. type
  3.   TCheckedDirections = array [0..7] of boolean;
  4.   TCheckCoordinate = record
  5.     Directions: TCheckedDirections;
  6.     x: integer;
  7.     y: integer;
  8.   end;
  9.   TPixelList = array of TCheckCoordinate;
  10.  
  11. var
  12.   PixelList: TPixelList;
  13.   DEM_NoDataValue,DEM_Height: single;
  14.   i:integer;
  15.   removePixel: boolean;
  16.  
  17.   procedure IncPixelList(Ax,Ay,AOrigin:integer);
  18.   var Fi:integer;
  19.   begin
  20.     setLength(PixelList, length(PixelList)+1);
  21.     for Fi:=0 to 7 do
  22.     begin
  23.       if Fi=AOrigin then {Set origin direction to true so we don't go backwards}
  24.         PixelList[high(PixelList)].Directions[Fi]:=true
  25.       else
  26.         PixelList[high(PixelList)].Directions[Fi]:=false;
  27.     end;
  28.     PixelList[high(PixelList)].x:=Ax;
  29.     PixelList[high(PixelList)].y:=Ay;
  30.   end;
  31.  
  32.   procedure DecPixelList;
  33.   begin
  34.     setLength(PixelList, length(PixelList)-1);
  35.   end;
  36.  
  37.   function CheckPixel(Ax,Ay,Ai:integer):boolean;
  38.   begin
  39.     result:=false;
  40.  
  41.     //Set the coordinates to check
  42.     case Ai of
  43.       0: begin Ax:=Ax+1;            end;
  44.       1: begin Ax:=Ax+1; Ay:=Ay+1;  end;
  45.       2: begin           Ay:=Ay+1;  end;
  46.       3: begin Ax:=Ax-1; Ay:=Ay+1;  end;
  47.       4: begin Ax:=Ax-1;            end;
  48.       5: begin Ax:=Ax-1; Ay:=Ay-1;  end;
  49.       6: begin           Ay:=Ay-1;  end;
  50.       7: begin Ax:=Ax+1; Ay:=Ay-1;  end;
  51.     end;
  52.  
  53.     //If the coordinates are within bounds and the FloodMaps can be drawn
  54.     //add the pixel to the PixelList.
  55.     if (Ax>=0) AND (Ax<Flood.Width) AND (Ay>=0) AND (Ay<Flood.Height) then
  56.     begin
  57.       if FlowMap[Ax,Ay] >= dist then
  58.         if FloodHeightMap[Ax,Ay] < fillHeight then
  59.         begin
  60.           DEM.GetPixel(Ax,Ay,single(DEM_Height));
  61.           if (DEM_Height<>DEM_NoDataValue) AND (DEM_Height<fillHeight) then
  62.           begin
  63.             FloodHeightMap[Ax,Ay]:=fillHeight;
  64.             FloodDepthMap[Ax,Ay]:=fillHeight-DEM_Height;
  65.             IncPixelList(Ax,Ay,(Ai+4) mod 8);
  66.             result:=true;
  67.           end;
  68.         end;
  69.     end;
  70.   end;
  71.  
  72. begin
  73.   DEM.GetNoDataValue(single(DEM_NoDataValue));
  74.   setLength(PixelList,0);
  75.   IncPixelList(x,y,-1);
  76.  
  77.   while length(PixelList)>0 do
  78.   begin
  79.     x:=PixelList[high(PixelList)].x;
  80.     y:=PixelList[high(PixelList)].y;
  81.     removePixel:=true;
  82.     for i:=0 to 7 do
  83.     begin
  84.       if PixelList[high(PixelList)].Directions[i]=false then
  85.       begin
  86.         PixelList[high(PixelList)].Directions[i]:=true;
  87.         removePixel:=false;
  88.         if CheckPixel(x,y,i) then break; {If FloodMaps can be drawn break the loop and continue with the next pixel}
  89.       end;
  90.     end;
  91.     if removePixel then DecPixelList; {All directions checked, remove last pixel from PixelList and continue with prvious pixel}
  92.   end;
  93. end;      

 

TinyPortal © 2005-2018