sixel rebuilding is broken since second pass change

[dankamongmen]

Issue #2573 brought substantial speed gains, but also left sixel rebuild in a nonfunctional condition. I'm pretty sure we're building up the auxvec correctly in sixel_wipe(), but we need adapt sixel_rebuild() to the new data arrangement. Currently, rebuilding simply has no effect (except on the TAM); this can easily be seen in [intro], when the orca is to the left of the HUD.

We need to fix this before we can release 3.0.6.

[dankamongmen]

ok, debugging of auxvec_idx() indicates that we're emitting some bogons out of there, and it will need be fixed before anything can work along these lines.

[dankamongmen]

ok, i've got us up through the actual encoding restore -- we have the two critical loops that walk the auxvec within our band, and i've tested them pretty thoroughly. i've also worked out some lingering issues in auxvec construction over in wipe_sixel(). so i'll do this last part, and this ought be resolved.

the downer here is that i've introduced a p^2 (worst-case) algorithm to restoration =. this won't fly, obviously, but i'm hoping mosaics will render it moot. improving it will be tough, though there are definitely a few simple things we can throw in to improve the average case dramatically. that worst-case is difficult to work around with our new sparse scheme, though. i think we'd need to keep copies of the unexpurged band vectors. let's hope it doesn't come to that.

[dankamongmen]

oh actually we could do it in O(P) time and O(C) space by just doing each auxvec entry by itself, and not looking for others. we'd need the O(C) space to keep an index into potentially each color's buf, or else we're right back to O(P*E) on encoding length E (and this would be an average case, not a worse case). well, let's keep that in our back pocket.

[dankamongmen]

also, valgrind is warning about an uninitialized element of the needs_refresh matrix, so make sure we get that handled.

[dankamongmen]

finishing this up in the dankamongmen/sixel-finalize branch.

[dankamongmen]

alright, we're copying in the rest now, and are almost there. we get some crud in the rebuild:

if i write color 0 to all elements of the auxvec, it improves, but is not perfect:

so there's almost certainly an issue in the reload calculations. let's test with them all hardcoded to 0 and see if that at least blacks everything out. if it does, our problem is in write_auxvec(). if not, our problem is at least partially in rebuild_band().

[dankamongmen]

nope, we get the same essential pattern hardcoding 0s in rebuild, so our problem is likely there.

[dankamongmen]

RESTORING band 72 (5->6 (437->460), 99->110) 11 pixels                                                                              
RESTORING band 73 (0->6 (437->460), 99->110) 66 pixels                                                                              
RESTORING band 74 (0->6 (437->460), 99->110) 66 pixels                                                                              
RESTORING band 75 (0->6 (437->460), 99->110) 66 pixels       

that's on a 23-high cell. we ought be getting 4 more rows restored for this cell, no? 23 * 19 == 437. but 438 % 6 == 0. so 1 row is indeed all we should get from band 72. we ought be getting four from band 76/

[dankamongmen]

better!

[dankamongmen]

RESTORING band 72 (5->6 (437->460), 99->110) 11 pixels                                                                              
RESTORING band 73 (0->6 (437->460), 99->110) 66 pixels                                                                              
RESTORING band 74 (0->6 (437->460), 99->110) 66 pixels                                                                              
RESTORING band 75 (0->6 (437->460), 99->110) 66 pixels                                                                              
RESTORING band 76 (0->4 (437->460), 99->110) 44 pixels   

yeah that looks right now. it looks like we're still missing a (more regular now) periodic pixel row...

[dankamongmen]

RESTORING band 72 (5->6 (437->460), 99->110) 11 pixels                                                                              
 looking at line 5 (auxvec row 5 idx 110, dy 0)                                                                                     
 idx 110 (dx 0 x 99): 1                                                                                                             
 idx 110 (dx 1 x 100): 1                                                                                                            
 idx 110 (dx 2 x 101): 1                                                                                                            
 idx 110 (dx 3 x 102): 1                                                                                                            
 idx 110 (dx 4 x 103): 1                                                                                                            
 idx 110 (dx 5 x 104): 1                                                                                                            
 idx 110 (dx 6 x 105): 1                                                                                                            
 idx 110 (dx 7 x 106): 1                                                                                                            
 idx 110 (dx 8 x 107): 1                                                                                                            
 idx 110 (dx 9 x 108): 1                                                                                                            
 idx 110 (dx 10 x 109): 1          

if that's idx into the auxvec, that's definitely wrong. that ought be row 0.

[dankamongmen]

RESTORING band 72 (5->6 (437->460), 99->110) 11 pixels                                                                              
 looking at line 5 (auxvec row 0 idx 0, dy 5)                                                                                       
 idx 0 (dx 0 x 99): 65535                                                                                                           
 idx 0 (dx 1 x 100): 65535                                                                                                          
 idx 0 (dx 2 x 101): 65535                                                                                                          
 idx 0 (dx 3 x 102): 65535                                                                                                          
 idx 0 (dx 4 x 103): 65535                                                                                                          
 idx 0 (dx 5 x 104): 65535                                                                                                          
 idx 0 (dx 6 x 105): 65535                                                                                                          
 idx 0 (dx 7 x 106): 65535                                                                                                          
 idx 0 (dx 8 x 107): 65535                                                                                                          
 idx 0 (dx 9 x 108): 65535                                                                                                          
 idx 0 (dx 10 x 109): 65535                                                                                                         
RESTORING band 73 (0->6 (437->460), 99->110) 66 pixels                                                                              
 looking at line 0 (auxvec row 0 idx 0, dy 0)                                                                                       
 idx 0 (dx 0 x 99): 65535                                                                                                           
 idx 0 (dx 1 x 100): 65535                                                                                                          
 idx 0 (dx 2 x 101): 65535                                                                                                          
 idx 0 (dx 3 x 102): 65535                                                                                                          
 idx 0 (dx 4 x 103): 65535                                                                                                          
 idx 0 (dx 5 x 104): 65535                                                                                                          
 idx 0 (dx 6 x 105): 65535                                                                                                          
 idx 0 (dx 7 x 106): 65535                                                                                                          
 idx 0 (dx 8 x 107): 65535                                                                                                          
 idx 0 (dx 9 x 108): 65535                                                                                                          
 idx 0 (dx 10 x 109): 65535                

that's fixed, but now the second ought show 1, and it's instead showing 0. indeed, this loops back on itself after 110, and is almost certainly responsible for our pattern.

[dankamongmen]

alright, we now get an all-solid pattern when i handset color in restore_band(). so we're placing things correctly now, but either storing or loading them incorrectly. almost done!

[dankamongmen]

writing all 0s from write_auxvec() results in the same pattern, except all one color, so i guess our bug is there.

[dankamongmen]

hrmm, no, even when writing all 0s, we get some of the following in restore:

  idx 198 (dx 10 x 10): 0                                                                                                           
 looking at bandline 2 (auxvec row 10 idx 220, dy 2)                                                                                
  idx 220 (dx 0 x 0): 0                                                                                                             
  idx 220 (dx 1 x 1): 0                                                                                                             
  idx 220 (dx 2 x 2): 0                                                                                                             
  idx 220 (dx 3 x 3): 0                                                                                                             
  idx 220 (dx 4 x 4): 0                                                                                                             
  idx 220 (dx 5 x 5): 0                                                                                                             
  idx 220 (dx 6 x 6): 0                                                                                                             
  idx 220 (dx 7 x 7): 0                                                                                                             
  idx 220 (dx 8 x 8): 0                                                                                                             
  idx 220 (dx 9 x 9): 0                                                                                                             
  idx 220 (dx 10 x 10): 0                                                                                                           
 looking at bandline 3 (auxvec row 11 idx 242, dy 3)                                                                                
  idx 242 (dx 0 x 0): 65535                                                                                                         
  idx 242 (dx 1 x 1): 65535                                                                                                         
  idx 242 (dx 2 x 2): 65535                                                                                                         
  idx 242 (dx 3 x 3): 65535                                                                                                         
  idx 242 (dx 4 x 4): 65535                                                                                                         
  idx 242 (dx 5 x 5): 65535                                                                                                         
  idx 242 (dx 6 x 6): 65535                                                                                                         
  idx 242 (dx 7 x 7): 65535                                                                                                         
  idx 242 (dx 8 x 8): 65535                                                                                                         
  idx 242 (dx 9 x 9): 65535                                                                                                         
  idx 242 (dx 10 x 10): 65535               

so our problem is presumably there.

[dankamongmen]

ahhh, found it! we now get blocks from wipe...and that ought resolve it all....

[dankamongmen]

very close! this is without any artificials

[dankamongmen]

ok, we no longer have any gaps, but things are a bit blockier than they ought be. still a regression, but a small one! closer!

[dankamongmen]

ok, i've got a good lead on this last bit of brokenness: if i fake the auxvec to be all 65535 (transparent) through the first 6 pixels of the (11px wide) cell, and color 0 through the rest, everything is transparent. if i reverse that, everything is black. i've verified the mix via output, so it seems that perhaps we're pulling from one side or the other to rebuild? ugh.

[dankamongmen]

similarly....if i tag even columns with 0 and odds with 65535, we get all black. if i invert that, we get all transparent. how does that work with the previous one? are we perhaps pulling everything from a single column? that would explain the blockiness!

[dankamongmen]

and with

  srand(time(NULL));                                                                                                                
int add = rand() % 2 ? 1 : 0;                                                                                                       
  for(int y = 0 ; y < tp / x ; ++y){                                                                                                
    for(int x0 = 0 ; x0 < x ; ++x0){                                                                                                
      uint16_t color;                                                                                                               
      memcpy(&color, &auxvec[(x0 + y * x) * 2], 2);                                                                                 
      fprintf(stderr, "%03d ", color);                                                                                              
color = ((x0 + add) % 2) * 65535;                                                                                                   
fprintf(stderr, "FAKING COLOR %hu\n", color);                                                                                       
memcpy(&auxvec[(x0 + y * x) * 2], &color, 2);  

we get one or the other about half the time. it's gotta be pulling from a single column. fucker.

[dankamongmen]

YEP

[dankamongmen]

yep, we work now =] W00T.

[dankamongmen]

i believe our complete sixel pipeline to be working once more, with the new sparse, multithreaded system. let's cut 3.0.6.