Sorting a small number of bytes. lazarus / 21-General ---------------------------------------------------------------------- MarkMLl · 2022-11-22 19:08 Given an array containing either three bytes or for the sake of optimisation four bytes where one is a zero dummy, or the equivalent 32-bit word, does anybody have a good hack for sorting the values? I don't need to know which is which since all I'm doing is extracting the saturation as a percentage: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i function saturation(p: TPixel): integer; inline; var  p2: array[0..SizeOf(TPixel) - 1] of byte; begin  TPixel(p2) := p;  BubbleSort(p2);  if SizeOf(TPixel) = 4 then            (* Element [0] will always be zero      *)    result := Round(100.0 * (p2[3] - p2[1]) / p2[3])  else    result := Round(100.0 * (p2[2] - p2[0]) / p2[2])end { saturation } ;  I've looked at the perennial bit-twiddling site but they've got nothing relevant. MarkMLl ---------------------------------------------------------------------- KodeZwerg · 2022-11-22 19:57 https://rmklever.com/?tag=saturation Taken from there and successful compiled with Lazarus, it works, maybe it help you - maybe I full misunderstood. ---------------------------------------------------------------------- MarkMLl · 2022-11-22 20:20 I don't want adjust anything, I want a simple metric per individual pixel to generate a mask. MarkMLl ---------------------------------------------------------------------- Thaddy · 2022-11-22 21:03 If you are very sure the data to sort is small, use a selection sort. But if, only if.. A selection sort is better than a bubble sort, but not efficient enough on larger data. Otherwise simply use a quick sort.. (or a heap sort ) ---------------------------------------------------------------------- MarkMLl · 2022-11-22 21:20 Quote from: Thaddy on November 22, 2022, 10:03:22 pmIf you are very sure the data to sort is small, use a selection sort. But if, only if.. A selection sort is better than a bubble sort, but not efficient enough on larger data. Otherwise simply use a quick sort.. (or a heap sort ) Yes, I am very sure. As I said, three elements per time (possibly plus a zero element which speeds things up elsewhere). Again as per my example: I'm extracting, per RGB pixel, the corresponding saturation value. The reason I'm writing this is that I /only/ want the saturation value per individual pixel, so that I can generate a mask that selects saturated colours from an overlay that's been applied to a photo: the other utilities I've looked at so far try to preserve hue etc. which I very much /don't/ want. MarkMLl ---------------------------------------------------------------------- 440bx · 2022-11-22 22:03 Presuming that this is a sort that will need to be done a large number of times, having it inline is probably desirable.  It seems that an inline selection sort is likely the best/optimal solution. And since the loop is so simple and there are so few elements, just unroll it. HTH. ---------------------------------------------------------------------- jamie · 2022-11-22 22:18 Looking to convert to chroma ? G=0.59,R=0.30 and B=0.11 Close enough.  Multiply the color channels times those scales and sum them.  Unless you are looking for something else but if that is what you are looking for then there is already code in a graphics unit somewhere that already does that. ---------------------------------------------------------------------- winni · 2022-11-22 22:20 Hi! One hint: BGRAbitmap allows you to convert BGR values into HSL  (Hue, Saturation, Lightning), each one as a word. Maybe that is an easier way. Winni ---------------------------------------------------------------------- avk · 2022-11-23 05:50 Quote from: MarkMLl on November 22, 2022, 08:08:34 pmGiven an array containing either three bytes or for the sake of optimisation four bytes where one is a zero dummy, or the equivalent 32-bit word, does anybody have a good hack for sorting the values? <...> Maybe something like this: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure SortFirst3(var a: array of Byte); // maybe inline?var  b: Byte;begin  Assert(Length(a) > 2);  if a[1] < a[0] then begin    b := a[0]; a[0] := a[1]; a[1] := b;  end;  if a[2] < a[1] then begin    b := a[1]; a[1] := a[2]; a[2] := b;  end;  if a[1] < a[0] then begin    b := a[0]; a[0] := a[1]; a[1] := b;  end;end; function saturation(p: TPixel): integer; inline;var  p2: array[0..SizeOf(TPixel) - 1] of byte;begin  TPixel(p2) := p;  if SizeOf(TPixel) = 4 then begin    SortFirst3(p2[1..3]);    result := Round(100.0 * (p2[3] - p2[1]) / p2[3]);  end else begin    SortFirst3(p2);    result := Round(100.0 * (p2[2] - p2[0]) / p2[2]);  end; might be good enough? You could even unfold SortFirst3() right inside saturation(). ---------------------------------------------------------------------- MarkMLl · 2022-11-23 07:03 Quote from: jamie on November 22, 2022, 11:18:55 pmLooking to convert to chroma ? How many times do I have to say this: I'm computing the saturation per-pixel to generate a mask. MarkMLl ---------------------------------------------------------------------- MarkMLl · 2022-11-23 07:03 Quote from: winni on November 22, 2022, 11:20:51 pmBGRAbitmap allows you to convert BGR values into HSL  (Hue, Saturation, Lightning), each one as a word. How many times do I have to say this: I'm computing the saturation per-pixel to generate a mask. MarkMLl ---------------------------------------------------------------------- MarkMLl · 2022-11-23 07:07 Quote from: avk on November 23, 2022, 06:50:20 amMaybe something like this: Thanks for that, I'll check it over once I've finished coding the binary subformats. The main bottleneck right now is reading the input file in text form, since it's substantially larger than 1Mb. At a pinch, this is something that would- subject to file access- parallelise trivially, since absolutely everything is per-pixel (i.e. there's no precomputation of a mean saturation across the image or anything like that). But OTOH it will only be run once daily, since that is how often I can get the raw files. MarkMLl ---------------------------------------------------------------------- MarkMLl · 2022-11-23 07:09 Quote from: 440bx on November 22, 2022, 11:03:31 pmPresuming that this is a sort that will need to be done a large number of times, having it inline is probably desirable.  It seems that an inline selection sort is likely the best/optimal solution. And since the loop is so simple and there are so few elements, just unroll it. Yes, generally agreed but I'm almost certainly up against the compiler's limit on the size of the code that can be inlined. MarkMLl ---------------------------------------------------------------------- Thaddy · 2022-11-23 07:16 Quote from: MarkMLl on November 23, 2022, 08:09:13 amYes, generally agreed but I'm almost certainly up against the compiler's limit on the size of the code that can be inlined. The compiler chooses a sensible limit. There is the option -OoLOOPUNROLL. I once determined a depth of 5, but that is pure determination and not founded in knowledge. I am not sure about code size. BTW, saturation is something that the compiler has always done right since the introduction of MMX instructions. You may want to investigate that. ---------------------------------------------------------------------- MarkMLl · 2022-11-23 07:24 Quote from: Thaddy on November 23, 2022, 08:16:59 amThe compiler chooses a sensible limit. ... I am not sure about code size. Based on the number of AST nodes. In principle it could be changed for special applications, but in general I'm happy to trust the compiler developers' judgement (I think Sven's discussed some of the rationale in the past). MarkMLl ---------------------------------------------------------------------- Thaddy · 2022-11-23 07:28 Posts crossed, Mark, you might re-read my reply, so the edit doesn't go un-noticed. (MMX remark) ---------------------------------------------------------------------- MarkMLl · 2022-11-23 08:01 Generally agreed, but I had a firkle around the compiler sources about a year ago and there was (working from memory) a single numeric constant limiting the acceptable node count. Of course, using MMX etc. for this would be another option. But I've already had grief with that sort of thing this week, where something warned me there were problems with its default settings because the computer I was using didn't have AVX2 (and then the fallback failed silently because it didn't have AVX either :-) MarkMLl ---------------------------------------------------------------------- winni · 2022-11-23 09:25 Quote from: MarkMLl on November 23, 2022, 08:03:33 amQuote from: winni on November 22, 2022, 11:20:51 pmBGRAbitmap allows you to convert BGR values into HSL  (Hue, Saturation, Lightning), each one as a word. How many times do I have to say this: I'm computing the saturation per-pixel to generate a mask. MarkMLl That's what I told you. Winni ---------------------------------------------------------------------- mika · 2022-11-23 09:36 Quote from: avk on November 23, 2022, 06:50:20 amMaybe something like this: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i procedure SortFirst3(var a: array of Byte); // maybe inline?var  b: Byte;begin  Assert(Length(a) > 2);  if a[1] < a[0] then begin    b := a[0]; a[0] := a[1]; a[1] := b;  end;  if a[2] < a[1] then begin    b := a[1]; a[1] := a[2]; a[2] := b;  end;  if a[1] < a[0] then begin    b := a[0]; a[0] := a[1]; a[1] := b;  end;end; function saturation(p: TPixel): integer; inline;var  p2: array[0..SizeOf(TPixel) - 1] of byte;begin  TPixel(p2) := p;  if SizeOf(TPixel) = 4 then begin    SortFirst3(p2[1..3]);    result := Round(100.0 * (p2[3] - p2[1]) / p2[3]);  end else begin    SortFirst3(p2);    result := Round(100.0 * (p2[2] - p2[0]) / p2[2]);  end; might be good enough? Idea is right. Use Sorting network. Implementation is bad. Read 3 elements of array in registers. Sort them, use them, no need to write back in array. As it is byte values you can replace division with multiplication by use of lookup table.  It will be all integer math then. ---------------------------------------------------------------------- MarkMLl · 2022-11-23 09:49 Quote from: winni on November 23, 2022, 10:25:04 amThat's what I told you. I do not want to convert to HSV, if I did I'd use one of the standard utilities. I want to extract ONLY the saturation, relative to a threshold point. I've also got other requirements relating to matching from a list of very specific RGB values. If one of the standard utilities did it I'd have used it. MarkMLl ---------------------------------------------------------------------- MarkMLl · 2022-11-23 09:51 Quote from: mika on November 23, 2022, 10:36:07 amIdea is right. Use Sorting network. Implementation is bad. Thanks, I'll take another look later. In practice switching to the binary representation gets the run down to a couple of seconds which is entirely adequate for something run a couple of times a day. MarkMLl ---------------------------------------------------------------------- 440bx · 2022-11-23 13:16 Quote from: MarkMLl on November 23, 2022, 08:09:13 amYes, generally agreed but I'm almost certainly up against the compiler's limit on the size of the code that can be inlined. MarkMLl I meant inlining the code manually.  Basically, what @avk showed but not in a function, instead directly in the "saturation" function. ---------------------------------------------------------------------- Thaddy · 2022-11-23 14:43 Quote from: 440bx on November 23, 2022, 02:16:39 pmI meant inlining the code manually.  Basically, what @avk showed but not in a function, instead directly in the "saturation" function. That is a wrong assumption, because inline is just a hint. Unless you mean you are writing the code out in assembler. ---------------------------------------------------------------------- avk · 2022-11-23 15:04 A little quick and dirty benchmark: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i program test;{$mode objfpc}uses  SysUtils; procedure BubbleSort(var a: array of byte);var  I, SwapPos, Last: Integer;  b: byte;begin  Last := High(a);  repeat    SwapPos := 0;    for I := 1 to Last do      if a[I - 1] > a[I] then begin        b := a[I];        a[I] := a[I - 1];      a[I - 1] := b;        SwapPos := I - 1;      end;    Last := SwapPos;  until SwapPos = 0;end; procedure SortFirst3(var a: array of Byte); inline;var  b: Byte;begin  Assert(Length(a) > 2);  if a[1] < a[0] then begin    b := a[0]; a[0] := a[1]; a[1] := b;  end;  if a[2] < a[1] then begin    b := a[1]; a[1] := a[2]; a[2] := b;  end;  if a[1] < a[0] then begin    b := a[0]; a[0] := a[1]; a[1] := b;  end;end; type  TPixel = DWord; function saturation0(p: TPixel): integer; inline;var  p2: array[0..SizeOf(TPixel) - 1] of byte;begin  TPixel(p2) := p;  if SizeOf(TPixel) = 4 then begin    BubbleSort(p2[1..3]);    result := Round(100.0 * (p2[3] - p2[1]) / p2[3]);  end else begin    BubbleSort(p2);    result := Round(100.0 * (p2[2] - p2[0]) / p2[2]);  end;end; function saturation1(p: TPixel): integer; inline;var  p2: array[0..SizeOf(TPixel) - 1] of byte;begin  TPixel(p2) := p;  if SizeOf(TPixel) = 4 then begin    SortFirst3(p2[1..3]);    result := Round(100.0 * (p2[3] - p2[1]) / p2[3]);  end else begin    SortFirst3(p2);    result := Round(100.0 * (p2[2] - p2[0]) / p2[2]);  end;end; function saturation2(px: TPixel): integer; inline;var  p2: array[0..SizeOf(TPixel) - 1] of byte;  p: PByte;  b: byte;begin  TPixel(p2) := px;  if SizeOf(TPixel) = 4 then  p := @p2[1]  else    p := @p2;   if p[1] < p[0] then begin    b := p[0]; p[0] := p[1]; p[1] := b;  end;  if p[2] < p[1] then begin    b := p[1]; p[1] := p[2]; p[2] := b;  end;  if p[1] < p[0] then begin    b := p[0]; p[0] := p[1]; p[1] := b;  end;   if SizeOf(TPixel) = 4 then    result := Round(100.0 * (p2[3] - p2[1]) / p2[3])  else    result := Round(100.0 * (p2[2] - p2[0]) / p2[2]);end; function saturation3(p: TPixel): integer; //inline;var  b, b0, b1, b2: byte;begin  if SizeOf(TPixel) = 4 then begin    b0 := Byte(p shr  8);    b1 := Byte(p shr 16);    b2 := Byte(p shr 24);  end else begin    b0 := Byte(p);    b1 := Byte(p shr  8);    b2 := Byte(p shr 16);  end;  if b1 < b0 then begin    b := b0; b0 := b1; b1 := b;  end;  if b2 < b1 then begin    b := b1; b1 := b2; b2 := b;  end;  if b1 < b0 then begin    b := b0; b0 := b1; b1 := b;  end;  result := Round(100.0 * (b2 - b0) / b2);end; var  a: array of DWord = nil;  I, J: Integer;  d: DWord;  Start: QWord;const  TestSize = 30000000;begin  SetLength(a, TestSize);  for I := 0 to High(a) do begin    d := Random(MaxInt);    if Byte(d shr 24) = 0 then      d := d or 1 shl 26;    a[I] := d;  end;  Start := GetTickCount64;  for I := 0 to High(a) do    J := saturation0(a[I]);  WriteLn('saturation0: ', GetTickCount64 - Start,' ms');  Start := GetTickCount64;  for I := 0 to High(a) do    J := saturation1(a[I]);  WriteLn('saturation1: ', GetTickCount64 - Start,' ms');  Start := GetTickCount64;  for I := 0 to High(a) do    J := saturation2(a[I]);  WriteLn('saturation2: ', GetTickCount64 - Start,' ms');  Start := GetTickCount64;  for I := 0 to High(a) do    J := saturation3(a[I]);  WriteLn('saturation3: ', GetTickCount64 - Start,' ms'); end.  result: Code: Text  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i saturation0: 453 mssaturation1: 390 mssaturation2: 390 mssaturation3: 281 ms It seems that the difference in reality is not so big. ---------------------------------------------------------------------- winni · 2022-11-23 15:58 Hi Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Procedure dumbsort (var a : array of byte);var i,k : Integer;      tmp: byte; beginfor i := 0 to high(a) -1 do  begin  for k := i+1 to high (a) do     begin     if a[k] < a[i] then        begin          tmp := a[i];          a[i] := a[k];          a[k] := tmp;         end; // if     end; // k  end; // iend;  // proc   Quicker than bubblesort Winni ---------------------------------------------------------------------- MarkMLl · 2022-11-23 19:23 I'm dropping this for the moment since as a proof-of-concept it's been part-successful, the limiting factor being the quality of the data I'm working from. I've been scraping images from two different areas on the same website: https://www.met.ie/latest-reports/surface-analysis and https://www.met.ie/latest-reports/satellites/europe-infrared-radar  These are only updated irregularly and- at best- have to be collected at different times to get the daily analysis and the matching rainfall radar: the analysis has pressure, temperature and derived fronts which makes it more detailed than what most met offices publish and I think the compilers are keenly aware of that (and reluctant to give too much away to people like me :-) My composite derivative is attached, and does a reasonable job of illustrating how rainfall tends to be on fronts: Eire (in particular) and Southwestern France had it wet in the early hours. The main problem I'm having is that it's difficult to distinguish between the blue used for moderate rainfall, and the blue used to highlight the sea: the saturation threshold I was hoping to use isn't entirely adequate, and since the file as received is a JPEG there's a lot of colour dithering which makes recognising features (either the rainfall we want to keep or the sea we want to discard) by colour alone tricky. It might be possible to resolve that by adjusting the saturation calculation: it was in part in anticipation of that need that I started coding something in the first place, and my guess would be that if I applied individual fudge factors to the components and/or used a log scale things would work better. I'll look at this again, probably sooner rather than later, but there are fewer and fewer authorities publishing this stuff in a form amenable to "old school" hacking: the UK Met Office replaced their rainfall radar a month or so ago with a "here's what we think is happening now based on our forecast of an hour ago" service which is nowhere near as useful. xref to older discussion: https://forum.lazarus.freepascal.org/index.php/topic,59009.0.html MarkMLl ---------------------------------------------------------------------- winni · 2022-11-23 19:42 Quote from: MarkMLl on November 23, 2022, 08:23:31 pmThe main problem I'm having is that it's difficult to distinguish between the blue used for moderate rainfall, and the blue used to highlight the sea: the saturation threshold I was hoping to use isn't entirely adequate, and since the file as received is a JPEG there's a lot of colour dithering which makes recognising features (either the rainfall we want to keep or the sea we want to discard) by colour alone tricky. MarkMLl Hi! Perhaps a solution: Use a copy of the JPEG-Image and apply a heavy blur so the dithering of the JPEG  vanishes. Then just compare the RGB values to separate the rain and the sea. Winni ---------------------------------------------------------------------- mika · 2022-11-23 19:49 Quote from: mika on November 23, 2022, 10:36:07 amAs it is byte values you can replace division with multiplication by use of lookup table.  i did time it. Has no time save what so ever. Never mind. ---------------------------------------------------------------------- MarkMLl · 2022-11-23 19:55 Quote from: winni on November 23, 2022, 08:42:20 pmUse a copy of the JPEG-Image and apply a heavy blur so the dithering of the JPEG  vanishes. Then just compare the RGB values to separate the rain and the sea. Possibly. Or alternatively use a different source e.g. https://meteoradar.co.uk/ which I'm already scraping as an overlay onto Google Earth, or possibly use Meteoradar to generate a mask for the slightly more colourful image from Eire. But I suspect that there's still scope for using a different saturation calculation: the shading that's causing artifacts in my current attempt /looks/ murkier than the radar overlay, and it should be possible to turn that subjective impression into maths. MarkMLl ---------------------------------------------------------------------- winni · 2022-11-23 21:11 Hi! Not an easy but a final solution: Download  the multi-polygon of the continental shapes, for example from https://www.naturalearthdata.com/ Use the continental shapes as a mask. The remainder must be sea. Winni ---------------------------------------------------------------------- MarkMLl · 2022-11-23 21:39 Quote from: winni on November 23, 2022, 10:11:48 pmUse the continental shapes as a mask. The remainder must be sea. "He had bought a large map representing the sea, without the least vestige of land..." Yes, had occurred to me for the "in extremis" situation. The problem there is that one can find oneself in a morass of conflicting or indeterminate projections and suddenly find it necessary to "do the job properly": I had a great deal of fun distorting the UK Met Office's Conic Conformal projection to an approximation of  the "Web Mercator" expected by the GIS engine underlying Google Earth. As another example, this sort of thing https://en.wikipedia.org/wiki/File:Europe-Liechtenstein.svg is very pretty and superficially useful, but decidedly non-rigorous. I'm also wondering whether- in this sort of application- saturation could usefully be treated as a three- (RGB) or six- (RGB+CMY) pointed star, with colours primary according to one or both of the customary schemes favoured. In any event, looking at the component values of the pixels that were getting through the filter really didn't make me happy: even if they were "correct" according to at least one of the saturation definitions. MarkMLl ---------------------------------------------------------------------- MarkMLl · 2022-11-24 12:01 I've had a bit more of a play with this after considering the nature of saturation etc. overnight, and have improved things enormously. The key is to produce two separate saturation figures, one of which is the dominant primary colour (i.e. R, G or B) vs the RMS of the other two components, and the other of which is the RMS of the two strongest components (potentially representing a complementary colour) vs the weakest one. Comparing each of those with the threshold value, and combining the result logically (i.e. not attempting to combine the saturations arithmetically) gives me a good mask with a minimum of noise from the sea etc. I'll probably stick the program onto Github after I've tinkered with the sorting a bit (many thanks to everybody for that) but in the interim I'd happily send a copy to anybody who wants it. Next day: I've been able to reject even more of the noise by adding a term to take into account how far the hue of a pixel is off one of the "pure colour" axes. I'm definitely losing out on some of the orange etc. shades, but the end result is good enough for what I want and is probably about as good as I can expect unless I start paying one of the met offices for data in a form with explicit layers (or start hacking various Javascript apps to intercept the more trendy forms of presentation). MarkMLl