Guest User

Untitled

a guest
May 9th, 2018
237
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. //#define FAILPOINT
  2.  
  3. using System;
  4. using System.Collections.Generic;
  5. using System.Collections.ObjectModel;
  6. using System.ComponentModel;
  7. using System.Runtime.InteropServices;
  8. using System.Runtime.ConstrainedExecution;
  9. using System.Configuration;
  10. using System.Diagnostics;
  11. using System.Reflection;
  12. using System.IO;
  13. using System.Security;
  14. using System.Linq;
  15. using System.Runtime.CompilerServices;
  16. using System.Text;
  17. using System.Threading;
  18. using System.Threading.Tasks;
  19. using System.Windows;
  20.  
  21. using alib;
  22. using alib.Array;
  23. using alib.Bits;
  24. using alib.Collections;
  25. using alib.Debugging;
  26. using alib.Enumerable;
  27.  
  28. namespace ConsoleApp5
  29. {
  30.     [SuppressUnmanagedCodeSecurity]
  31.     static class candidates
  32.     {
  33.         static candidates()
  34.         {
  35.             msb_tab_7 = setup_7();
  36.             msb_tab_8 = setup_8();
  37.             msb_tab_15 = setup_15();
  38.             msb_tab_16 = setup_16();
  39.             //msb_tab_nyb = setup_nyb();
  40.         }
  41.  
  42.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  43.         readonly static byte[] msb_tab_7, msb_tab_8, msb_tab_15, msb_tab_16;
  44.  
  45.         static byte[] setup_16()
  46.         {
  47.             int i, c;
  48.             byte n;
  49.             var p = new byte[0x10000];
  50.  
  51.             p[0] = 0xFF;
  52.             for (n = 0; n < 16; n++)
  53.                 for (c = 1 << n, i = 0; i < c; i++)
  54.                     p[c + i] = n;
  55.             return p;
  56.         }
  57.  
  58.  
  59.         //static byte[] setup_nyb()
  60.         //{
  61.         //  int i, c, j;
  62.         //  byte n;
  63.         //  var p = new byte[0x4000];
  64.  
  65.         //  j = 0;
  66.         //  for (n = 0, c = 1; n < 16; c <<= 1, n++)
  67.         //      for (i = 0; i < c; i += 2)
  68.         //      {
  69.         //          p[j++] = n;
  70.         //      }
  71.         //  return p;
  72.         //}
  73.  
  74.  
  75.         //{
  76.         //  0x00, 0x01, 0x02, 0x02, 0x03, 0x03, 0x03, 0x03, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04, 0x04,
  77.         //  0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05, 0x05,
  78.         //  0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  79.         //  0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06, 0x06,
  80.         //  0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  81.         //  0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  82.         //  0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  83.         //  0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07, 0x07,
  84.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  85.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  86.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  87.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  88.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  89.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  90.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  91.         //  0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08, 0x08,
  92.         //};
  93.  
  94.  
  95.         static byte[] setup_7()
  96.         {
  97.             int i, c;
  98.             byte n;
  99.             var p = new byte[0x80];
  100.  
  101.             for (n = 0; n < 8; n++)
  102.                 for (c = (1 << n) >> 1, i = 0; i < c; i++)
  103.                     p[c + i] = n;
  104.             return p;
  105.         }
  106.         static byte[] setup_8()
  107.         {
  108.             int i, c;
  109.             byte n;
  110.             var p = new byte[0x100];
  111.  
  112.             p[0] = 0xFF;
  113.             for (n = 0; n < 8; n++)
  114.                 for (c = 1 << n, i = 0; i < c; i++)
  115.                     p[c + i] = n;
  116.             return p;
  117.         }
  118.  
  119.         static byte[] setup_15()
  120.         {
  121.             int i, c;
  122.             byte n;
  123.             var p = new byte[0x8000];
  124.  
  125.             for (n = 0; n < 16; n++)
  126.                 for (c = (1 << n) >> 1, i = 0; i < c; i++)
  127.                     p[c + i] = n;
  128.             return p;
  129.         }
  130.  
  131.         //static byte[] setup_nyb()
  132.         //{
  133.         //  int i, c, j;
  134.         //  byte n;
  135.         //  var p = new byte[0x4000];
  136.  
  137.         //  j = 0;
  138.         //  for (n = 0, c = 1; n < 16; c <<= 1, n++)
  139.         //      for (i = 0; i < c; i += 2)
  140.         //      {
  141.         //          p[j++] = n;
  142.         //      }
  143.         //  return p;
  144.         //}
  145.  
  146.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  147.         public static int HighestOne_Tab16A(ulong v)
  148.         {
  149.             if ((long)v <= 0)
  150.                 return (int)((v >> 57) & 0x40) - 1;
  151.  
  152.             int j = (int)((0xFFFFFFFFU - v) >> 58) & 0x20;
  153.  
  154.             j += (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
  155.  
  156.             return j + msb_tab_15[v >> (j + 1)];
  157.         }
  158.  
  159.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  160.         public static int HighestOne_Tab16B(ulong v)
  161.         {
  162.             if ((long)v <= 0)
  163.                 return (int)((v >> 57) & 0x40) - 1;
  164.  
  165.             int j;
  166.             return (j = (j = (int)((0xFFFFFFFFU - v) >> 58) & 0x20) |
  167.                              (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10) + msb_tab_15[v >> (j + 1)];
  168.         }
  169.  
  170.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  171.         public static int HighestOne_Tab16C(ulong v)
  172.         {
  173.             if ((long)v <= 0)
  174.                 return (int)((v >> 57) & 0x40) - 1;
  175.  
  176.             int j;
  177.             return (j = (j = (int)((0xFFFFFFFFU - v) >> 58) & 0x20) |
  178.                              (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10) + msb_tab_16[v >> j];
  179.         }
  180.  
  181.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  182.         public static int HighestOne_Tab16D(ulong v)
  183.         {
  184.             if ((long)v <= 0)
  185.                 return (int)((v >> 57) & 0x40) - 1;
  186.  
  187.             int j = (int)((0xFFFFFFFFU - v) >> 58) & 0x20;
  188.  
  189.             j += (int)((0x0000FFFFU - (v >> j)) >> 59) & 0x10;
  190.  
  191.             return j + msb_tab_16[v >> j];
  192.         }
  193.  
  194.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  195.         public static int HighestOne_Tab8A(ulong v)
  196.         {
  197.             if ((long)v <= 0)
  198.                 return (int)((v >> 57) & 64) - 1;
  199.  
  200.             int j;
  201.             j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
  202.             j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
  203.             j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
  204.             return j + msb_tab_8[v >> j];
  205.         }
  206.  
  207.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  208.         public static int HighestOne_Tab8B(ulong v)
  209.         {
  210.             if ((long)v <= 0)
  211.                 return (int)((v >> 57) & 64) - 1;
  212.  
  213.             int j;
  214.             j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
  215.             j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
  216.             j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
  217.             return j + msb_tab_7[v >> (j + 1)];
  218.         }
  219.  
  220.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  221.         public static int HighestOne_NoTab(ulong v)
  222.         {
  223.             if ((long)v <= 0)
  224.                 return (int)((v >> 57) & 64) - 1;
  225.  
  226.             int j;
  227.             j =  /**/ (int)((0xFFFFFFFFU - v) >> 58) & 32;
  228.             j += /**/ (int)((0x0000FFFFU - (v >> j)) >> 59) & 16;
  229.             j += /**/ (int)((0x000000FFU - (v >> j)) >> 60) & 8;
  230.             j += /**/ (int)((0x0000000FU - (v >> j)) >> 61) & 4;
  231.             j += /**/ (int)((0x00000003U - (v >> j)) >> 62) & 2;
  232.             j += /**/ (int)((0x00000001U - (v >> j)) >> 63) & 1;
  233.  
  234.             return j;
  235.         }
  236.  
  237.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  238.         public static int HighestOne_Naive(ulong ul)
  239.         {
  240.             if ((long)ul <= 0)
  241.                 return (int)((ul >> 57) & 64) - 1;
  242.  
  243.             int o = ul > 0xFFFFFFFFU ? 32 : 0;
  244.  
  245.             if ((ul >> o) > 0xFFFFU)
  246.                 o |= 16;
  247.             if ((ul >> o) > 0xFFU)
  248.                 o |= 8;
  249.             if ((ul >> o) > 0xFU)
  250.                 o |= 4;
  251.             if ((ul >> o) > 3U)
  252.                 o |= 2;
  253.             if ((ul >> o) > 1U)
  254.                 o |= 1;
  255.  
  256.             return o;
  257.         }
  258.  
  259.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  260.         public static int HighestOne_32(ulong ul)
  261.         {
  262.             if ((ul & 0xFFFFFFFF00000000) != 0)
  263.                 return alib.Bits._highest_one_bit.HighestOne((uint)(ul >> 32)) + 32;
  264.             return alib.Bits._highest_one_bit.HighestOne((uint)ul);
  265.         }
  266.     };
  267.  
  268.     ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  269.     ///
  270.     public static class de_Bruijn
  271.     {
  272.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  273.         const uint
  274.             N_bsf32 = 0X077CB531,
  275.             N_bsr32 = 0X07C4ACDD;
  276.  
  277.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  278.         readonly public static sbyte[]
  279.             bsf32 =
  280.             {
  281.                  0,  1, 28,  2, 29, 14, 24,  3, 30, 22, 20, 15, 25, 17,  4,  8,
  282.                 31, 27, 13, 23, 21, 19, 16,  7, 26, 12, 18,  6, 11,  5, 10,  9,
  283.             },
  284.             bsr32 =
  285.             {
  286.                  0,  9,  1, 10, 13, 21,  2, 29, 11, 14, 16, 18, 22,  25, 3, 30,
  287.                  8, 12, 20, 28, 15, 17, 24,  7, 19, 27, 23,  6, 26,  5,  4, 31
  288.             };
  289.  
  290.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  291.         public static int IndexOfLSB(uint v) => v != 0 ? bsf32[((v & (uint)-(int)v) * N_bsf32) >> 27] : -1;
  292.  
  293.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  294.         public static uint SetTrailing(uint v)
  295.         {
  296.             v |= v >> 1;
  297.             v |= v >> 2;
  298.             v |= v >> 4;
  299.             v |= v >> 8;
  300.             v |= v >> 16;
  301.             return v;
  302.         }
  303.  
  304.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  305.         readonly public static sbyte[]
  306.             bsf64 =
  307.             {
  308.                 63,  0, 58,  1, 59, 47, 53,  2, 60, 39, 48, 27, 54, 33, 42,  3,
  309.                 61, 51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22,  4,
  310.                 62, 57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21,
  311.                 56, 45, 25, 31, 35, 16,  9, 12, 44, 24, 15,  8, 23,  7,  6,  5,
  312.             },
  313.             bsr64 =
  314.             {
  315.                  0, 47,  1, 56, 48, 27,  2, 60, 57, 49, 41, 37, 28, 16,  3, 61,
  316.                 54, 58, 35, 52, 50, 42, 21, 44, 38, 32, 29, 23, 17, 11,  4, 62,
  317.                 46, 55, 26, 59, 40, 36, 15, 53, 34, 51, 20, 43, 31, 22, 10, 45,
  318.                 25, 39, 14, 33, 19, 30,  9, 24, 13, 18,  8, 12,  7,  6,  5, 63,
  319.             };
  320.  
  321.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  322.         const ulong
  323.             N_bsf64 = 0x07EDD5E59A4E28C2,
  324.             N_bsr64 = 0x03F79D71B4CB0A89;
  325.  
  326.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  327.         public static int IndexBSF(ulong v) => bsf64[(v * N_bsf64) >> 58];
  328.  
  329.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  330.         public static int IndexOfLSB(ulong v) => v != 0 ? bsf64[((v & (ulong)-(long)v) * N_bsf64) >> 58] : -1;
  331.  
  332.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  333.         public static int IndexClearLSB(ref ulong v)
  334.         {
  335.             if (v == 0)
  336.                 return -1;
  337.  
  338.             ulong m = v & (ulong)-(long)v;
  339.             v ^= m;
  340.             return bsf64[(m * N_bsf64) >> 58];
  341.         }
  342.  
  343.         public static int IndexOfMSB(ulong v)
  344.         {
  345.             if ((long)v <= 0)
  346.                 return (int)((v >> 57) & 64) - 1;
  347.  
  348.             v |= v >> 1;
  349.             v |= v >> 2;
  350.             v |= v >> 4;
  351.             v |= v >> 8;
  352.             v |= v >> 16;
  353.             v |= v >> 32;
  354.  
  355.             return bsr64[(v * N_bsr64) >> 58];
  356.         }
  357.  
  358.         /// <summary> rotate qword to the right until the highest bit is set (if possible).
  359.         /// Useful prior to dividing by a prime for hashing, but be sure to include raw info as well since
  360.         /// this operation is highly conflating of sparse values </summary>
  361.         public static ulong RorToNeg(this ulong v)
  362.         {
  363.             int ix = IndexOfLSB(v) + 1;
  364.             return (long)v > 0 ? (v >> ix) | (v << (64 - ix)) : v;
  365.         }
  366.  
  367.  
  368.         /// this one...
  369.         //PasMPBSRDebruijn64Multiplicator:TPasMPUInt64=TPasMPUInt64($03f79d71b4cb0a89);
  370.         //PasMPBSRDebruijn64Shift=58;
  371.         //    PasMPBSRDebruijn64Mask=63;
  372.         //    PasMPBSRDebruijn64Table:array[0..63] of TPasMPInt32=(0,47,1,56,48,27,2,60,57,49,41,37,28,16,3,61,54,58,35,52,50,42,21,44,38,32,29,23,17,11,4,62,
  373.         //                                                         46,55,26,59,40,36,15,53,34,51,20,43,31,22,10,45,25,39,14,33,19,30,9,24,13,18,8,12,7,6,5,63);
  374.  
  375. #if false
  376.         PasMPCLZDebruijn32Multiplicator=TPasMPUInt32($07c4acdd);
  377.         PasMPCLZDebruijn32Shift=27;
  378.       PasMPCLZDebruijn32Mask=31;
  379.       PasMPCLZDebruijn32Table:array[0..31] of TPasMPInt32=(31,22,30,21,18,10,29,2,20,17,15,13,9,6,28,1,23,19,11,3,16,14,7,24,12,4,8,25,5,26,27,0);
  380.  
  381.       PasMPCLZDebruijn64Multiplicator:TPasMPUInt64=TPasMPUInt64($03f79d71b4cb0a89);
  382.         PasMPCLZDebruijn64Shift=58;
  383.       PasMPCLZDebruijn64Mask=63;
  384.       PasMPCLZDebruijn64Table:array[0..63] of TPasMPInt32=(63,16,62,7,15,36,61,3,6,14,22,26,35,47,60,2,9,5,28,11,13,21,42,19,25,31,34,40,46,52,59,1,
  385.                                                            17,8,37,4,23,27,48,10,29,12,43,20,32,41,53,18,38,24,49,30,44,33,54,39,50,45,55,51,56,57,58,0);
  386.  
  387.       PasMPCTZDebruijn32Multiplicator=TPasMPUInt32($077cb531);
  388.         PasMPCTZDebruijn32Shift=27;
  389.       PasMPCTZDebruijn32Mask=31;
  390.       PasMPCTZDebruijn32Table:array[0..31] of TPasMPInt32=(0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9);
  391.  
  392.       PasMPCTZDebruijn64Multiplicator:TPasMPUInt64=TPasMPUInt64($07edd5e59a4e28c2);
  393.         PasMPCTZDebruijn64Shift=58;
  394.       PasMPCTZDebruijn64Mask=63;
  395.       PasMPCTZDebruijn64Table:array[0..63] of TPasMPInt32=(63,0,58,1,59,47,53,2,60,39,48,27,54,33,42,3,61,51,37,40,49,18,28,20,55,30,34,11,43,14,22,4,
  396.                                                            62,57,46,52,38,26,32,41,50,36,17,19,29,10,13,21,56,45,25,31,35,16,9,12,44,24,15,8,23,7,6,5);
  397.  
  398.       PasMPBSFDebruijn32Multiplicator=TPasMPUInt32($077cb531);
  399.         PasMPBSFDebruijn32Shift=27;
  400.       PasMPBSFDebruijn32Mask=31;
  401.       PasMPBSFDebruijn32Table:array[0..31] of TPasMPInt32=(0,1,28,2,29,14,24,3,30,22,20,15,25,17,4,8,31,27,13,23,21,19,16,7,26,12,18,6,11,5,10,9);
  402.  
  403.       PasMPBSFDebruijn64Multiplicator:TPasMPUInt64=TPasMPUInt64($03f79d71b4cb0a89);
  404.         PasMPBSFDebruijn64Shift=58;
  405.       PasMPBSFDebruijn64Mask=63;
  406.       PasMPBSFDebruijn64Table:array[0..63] of TPasMPInt32=(0,1,48,2,57,49,28,3,61,58,50,42,38,29,17,4,62,55,59,36,53,51,43,22,45,39,33,30,24,18,12,5,
  407.                                                           63,47,56,27,60,41,37,16,54,35,52,21,44,32,23,11,46,26,40,15,34,20,31,10,25,14,19,9,13,8,7,6);
  408.  
  409.       PasMPBSRDebruijn32Multiplicator=TPasMPUInt32($07c4acdd);
  410.         PasMPBSRDebruijn32Shift=27;
  411.       PasMPBSRDebruijn32Mask=31;
  412.       PasMPBSRDebruijn32Table:array[0..31] of TPasMPInt32=(0,9,1,10,13,21,2,29,11,14,16,18,22,25,3,30,8,12,20,28,15,17,24,7,19,27,23,6,26,5,4,31);
  413.  
  414.       PasMPBSRDebruijn64Multiplicator:TPasMPUInt64=TPasMPUInt64($03f79d71b4cb0a89);
  415.         PasMPBSRDebruijn64Shift=58;
  416.       PasMPBSRDebruijn64Mask=63;
  417.       PasMPBSRDebruijn64Table:array[0..63] of TPasMPInt32=(0,47,1,56,48,27,2,60,57,49,41,37,28,16,3,61,54,58,35,52,50,42,21,44,38,32,29,23,17,11,4,62,
  418.                                                            46,55,26,59,40,36,15,53,34,51,20,43,31,22,10,45,25,39,14,33,19,30,9,24,13,18,8,12,7,6,5,63);
  419. #endif
  420.  
  421.  
  422.  
  423. #if false
  424.         const deBruijn64 = 0x0218a392cd3d5dbf
  425.  
  426. var deBruijnIdx64 = [64]byte{
  427.     0, 1, 2, 7, 3, 13, 8, 19,
  428.     4, 25, 14, 28, 9, 34, 20, 40,
  429.     5, 17, 26, 38, 15, 46, 29, 48,
  430.     10, 31, 35, 54, 21, 50, 41, 57,
  431.     63, 6, 12, 18, 24, 27, 33, 39,
  432.     16, 37, 45, 47, 30, 53, 49, 56,
  433.     62, 11, 23, 32, 36, 44, 52, 55,
  434.     61, 22, 43, 51, 60, 42, 59, 58,
  435. }
  436.  
  437.         // Ctz64 counts trailing (low-order) zeroes,
  438.         // and if all are zero, then 64.
  439.         func Ctz64(x uint64) int {
  440.     x &= -x                      // isolate low-order bit
  441.     y := x* deBruijn64 >> 58    // extract part of deBruijn sequence
  442.     i := int (deBruijnIdx64[y])   // convert to bit index
  443.      z := int ((x - 1) >> 57 & 64) // adjustment if zero
  444.     return i + z
  445.     }
  446. #endif
  447.     };
  448.  
  449.  
  450.  
  451.     ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  452.     ///
  453.     [SuppressUnmanagedCodeSecurity]
  454.     public static unsafe class _highest_one_bit_UNMANAGED
  455.     {
  456.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  457.         readonly static sbyte* msb_tab_x2;
  458.  
  459.         static _highest_one_bit_UNMANAGED()
  460.         {
  461.             int i, c;
  462.             sbyte n;
  463. #if WIN32
  464.             using (new win32.VmProtector((UIntPtr)0x8000, out sbyte* p))
  465. #else
  466.             sbyte* p = (sbyte*)GCHandle.Alloc(new sbyte[0x8000], GCHandleType.Pinned).AddrOfPinnedObject();
  467. #endif
  468.             {
  469.                 msb_tab_x2 = p;
  470.  
  471.                 for (n = 0, c = 1; n < 16; c <<= 1, n++)
  472.                     for (i = 0; i < c; i += 2)
  473.                         *p++ = n;
  474.  
  475.                 Debug.Assert(p - msb_tab_x2 == 0x8000);
  476.             }
  477.         }
  478.  
  479.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  480.         public static int HighestOne(sbyte i8) => msb_tab_x2[(byte)i8 >> 1];
  481.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  482.         public static int HighestOne(byte ui8) => msb_tab_x2[ui8 >> 1];
  483.  
  484.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  485.         public static int HighestOne(char ch) => msb_tab_x2[ch >> 1];
  486.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  487.         public static int HighestOne(short i16) => msb_tab_x2[(ushort)i16 >> 1];
  488.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  489.         public static int HighestOne(ushort ui16) => msb_tab_x2[ui16 >> 1];
  490.  
  491.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  492.         public static int HighestOne(int i32) => HighestOne((uint)i32);
  493.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  494.         public static int HighestOne(uint ui) => ui > 0x0000FFFF ? msb_tab_x2[ui >> 17] + 16 : msb_tab_x2[ui >> 1];
  495.  
  496.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  497.         public static int HighestOne(long i64) => HighestOne_U((ulong)i64);
  498.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  499.         public static int HighestOne_U(ulong v)
  500.         {
  501.             if ((long)v <= 0)
  502.                 return (int)((v >> 57) & 64) - 1;
  503.  
  504.             int j = v < 0x0000000100000000UL ? (v < 0x0000000000010000UL ? 0 : 16) : (v < 0x0001000000000000UL ? 32 : 48);
  505.             return msb_tab_x2[v >> (j + 1)] + j;
  506.         }
  507.     };
  508.  
  509.     ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  510.     ///
  511.     [SuppressUnmanagedCodeSecurity]
  512.     public static class _old_1
  513.     {
  514.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  515.         readonly static sbyte[] highest_one_16;
  516.  
  517.         static _old_1()
  518.         {
  519.             int i, c, j;
  520.             sbyte n;
  521.  
  522.             var p = new sbyte[0x10000];
  523.  
  524.             p[0] = -1;
  525.             j = 1;
  526.             for (n = 0, c = 1; n < 16; c <<= 1, n++)
  527.                 for (i = 0; i < c; i++)
  528.                     p[j++] = n;
  529.  
  530.             highest_one_16 = p;
  531.         }
  532.  
  533.         //public static int HighestOne(sbyte i8) => highest_one_16[i8];
  534.         //public static int HighestOne(byte ui8) => highest_one_16[ui8];
  535.  
  536.         //public static int HighestOne(char ch) => highest_one_16[ch];
  537.         //public static int HighestOne(short i16) => highest_one_16[i16];
  538.         //public static int HighestOne(ushort ui16) => highest_one_16[ui16];
  539.  
  540.         //public static int HighestOne(int i32) => HighestOne((uint)i32);
  541.         //public static int HighestOne(uint ui32)
  542.         //{
  543.         //  int i;
  544.         //  return (i = highest_one_16[ui32 >> 16]) < 0 ?
  545.         //              highest_one_16[(ushort)ui32] : (i + 16);
  546.         //}
  547.  
  548.         //public static int HighestOne( long i64) => HighestOne((ulong)i64);
  549.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  550.         public static int HighestOne_Old1(ulong ui64)
  551.         {
  552.             int i, j;
  553.             return (i = highest_one_16[ui64 >> (j = 48)]) < 0 &&
  554.                    (i = highest_one_16[ui64 >> (j = 32)]) < 0 &&
  555.                    (i = highest_one_16[ui64 >> (j = 16)]) < 0 ?
  556.                         highest_one_16[(ushort)ui64] : (i + j);
  557.         }
  558.     };
  559.  
  560.  
  561.     ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  562.     ///
  563.     [SuppressUnmanagedCodeSecurity]
  564.     public static class _old_2
  565.     {
  566.         [DebuggerBrowsable(DebuggerBrowsableState.Never)]
  567.         readonly static sbyte[] msb_tab_x2;
  568.  
  569.         static _old_2()
  570.         {
  571.             int i, c, j;
  572.             sbyte n;
  573.             var p = new sbyte[0x8000];
  574.  
  575.             j = 0;
  576.             for (n = 0, c = 1; n < 16; c <<= 1, n++)
  577.                 for (i = 0; i < c; i += 2)
  578.                     p[j++] = n;
  579.  
  580.             msb_tab_x2 = p;
  581.  
  582.         }
  583.  
  584.         //public static int HighestOne(sbyte i8) => msb_tab_x2[(byte)i8 >> 1];
  585.         //public static int HighestOne(byte ui8) => msb_tab_x2[ui8 >> 1];
  586.  
  587.         //public static int HighestOne(char ch) => msb_tab_x2[ch >> 1];
  588.         //public static int HighestOne(short i16) => msb_tab_x2[(ushort)i16 >> 1];
  589.         //public static int HighestOne(ushort ui16) => msb_tab_x2[ui16 >> 1];
  590.  
  591.         //public static int HighestOne(int i32) => HighestOne((uint)i32);
  592.         //public static int HighestOne(uint ui) => ui > 0x0000FFFF ? msb_tab_x2[ui >> 17] + 16 : msb_tab_x2[ui >> 1];
  593.  
  594.         //public static int HighestOne( long i64) => HighestOne((ulong)i64);
  595.         [MethodImpl(MethodImplOptions.AggressiveInlining)]
  596.         public static int HighestOne_Old2(ulong ul)
  597.         {
  598.             return ul > 0x0000FFFFFFFFFFFF ? msb_tab_x2[ul >> 49] + 48 :
  599.                             ul > 0x00000000FFFFFFFF ? msb_tab_x2[ul >> 33] + 32 :
  600.                                 ul > 0x000000000000FFFF ? msb_tab_x2[ul >> 17] + 16 :
  601.                                     ul != 0 ? msb_tab_x2[ul >> 1] : -1;
  602.         }
  603.     };
  604. }
RAW Paste Data