API tools faq
paste
Advertisement
Guest User

Untitled

a guest
May 9th, 2018
539
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 19.16 KB | None | 0 0
raw download clone embed print report
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!