API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Jan 12th, 2018
311
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C# 19.05 KB | None | 0 0
raw download clone embed print report
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading.Tasks;
  6. using System.Threading;
  7. using System.IO;
  8. using System.Collections.Concurrent;
  9. using System.Runtime.InteropServices;
  10. using System.Security.Cryptography;
  11.  
  12. namespace md5
  13. {
  14.     static class ArrayExt
  15.     {
  16.         public static T[] SubArray<T>(this T[] data, int index, int length)
  17.         {
  18.             T[] result = new T[length];
  19.             Array.Copy(data, index, result, 0, length);
  20.             return result;
  21.         }
  22.     }
  23.     class FastMD5
  24.     {
  25.         static public void Get2(UInt32[] state, UInt32 key)
  26.         {
  27.             UInt32 a = state[0] = 0x67452301;
  28.             UInt32 b = state[1] = 0xEFCDAB89;
  29.             UInt32 c = state[2] = 0x98BADCFE;
  30.             UInt32 d = state[3] = 0x10325476;
  31.             UInt32 x;
  32.             //Руанд 0
  33.             x = (0xD76AA477 + key); a = ((x << 7) | (x >> (32 - 7))) + b;
  34.             x = ((0x98BADCFE ^ (a & (0x77777777))) + 0xF8FA0C4C); d = ((x << 12) | (x >> (32 - 12))) + a;
  35.             x = ((0xEFCDAB89 ^ (d & (a ^ 0xEFCDAB89))) + 0xBCDB4DD9); c = ((x << 17) | (x >> (32 - 17))) + d;
  36.             x = (0xEFCDAB89 + (a ^ (c & (d ^ a))) + 0xC1BDCEEE); b = ((x << 22) | (x >> (32 - 22))) + c;
  37.             x = (a + (d ^ (b & (c ^ d))) + 0xF57C0FAF); a = ((x << 7) | (x >> (32 - 7))) + b;
  38.             x = (d + (c ^ (a & (b ^ c))) + 0x4787C62A); d = ((x << 12) | (x >> (32 - 12))) + a;
  39.             x = (c + (b ^ (d & (a ^ b))) + 0xA8304613); c = ((x << 17) | (x >> (32 - 17))) + d;
  40.             x = (b + (a ^ (c & (d ^ a))) + 0xFD469501); b = ((x << 22) | (x >> (32 - 22))) + c;
  41.             x = (a + (d ^ (b & (c ^ d))) + 0x698098D8); a = ((x << 7) | (x >> (32 - 7))) + b;
  42.             x = (d + (c ^ (a & (b ^ c))) + 0x8B44F7AF); d = ((x << 12) | (x >> (32 - 12))) + a;
  43.             x = (c + (b ^ (d & (a ^ b))) + 0xFFFF5BB1); c = ((x << 17) | (x >> (32 - 17))) + d;
  44.             x = (b + (a ^ (c & (d ^ a))) + 0x895CD7BE); b = ((x << 22) | (x >> (32 - 22))) + c;
  45.             x = (a + (d ^ (b & (c ^ d))) + 0x6B901122); a = ((x << 7) | (x >> (32 - 7))) + b;
  46.             x = (d + (c ^ (a & (b ^ c))) + 0xFD987193); d = ((x << 12) | (x >> (32 - 12))) + a;
  47.             x = (c + (b ^ (d & (a ^ b))) + 0xA67943AE); c = ((x << 17) | (x >> (32 - 17))) + d;
  48.             x = (b + (a ^ (c & (d ^ a))) + 0x49B40821); b = ((x << 22) | (x >> (32 - 22))) + c;
  49.             //Раунд 1
  50.             x = (a + (c ^ (d & (b ^ c))) + 0xF61E25E2); a = ((x << 5) | (x >> (32 - 5))) + b;
  51.             x = (d + (b ^ (c & (a ^ b))) + 0xC040B340); d = ((x << 9) | (x >> (32 - 9))) + a;
  52.             x = (c + (a ^ (b & (d ^ a))) + 0x265E5A51); c = ((x << 14) | (x >> (32 - 14))) + d;
  53.             x = (b + (d ^ (a & (c ^ d))) + 0xE9B6C7AA + key); b = ((x << 20) | (x >> (32 - 20))) + c;
  54.             x = (a + (c ^ (d & (b ^ c))) + 0xD62F105D); a = ((x << 5) | (x >> (32 - 5))) + b;
  55.             x = (d + (b ^ (c & (a ^ b))) + 0x02441453); d = ((x << 9) | (x >> (32 - 9))) + a;
  56.             x = (c + (a ^ (b & (d ^ a))) + 0xD8A1E681); c = ((x << 14) | (x >> (32 - 14))) + d;
  57.             x = (b + (d ^ (a & (c ^ d))) + 0xE7D3FBC8); b = ((x << 20) | (x >> (32 - 20))) + c;
  58.             x = (a + (c ^ (d & (b ^ c))) + 0x21E1CDE6); a = ((x << 5) | (x >> (32 - 5))) + b;
  59.             x = (d + (b ^ (c & (a ^ b))) + 0xC33707F6); d = ((x << 9) | (x >> (32 - 9))) + a;
  60.             x = (c + (a ^ (b & (d ^ a))) + 0xF4D50D87); c = ((x << 14) | (x >> (32 - 14))) + d;
  61.             x = (b + (d ^ (a & (c ^ d))) + 0x455A14ED); b = ((x << 20) | (x >> (32 - 20))) + c;
  62.             x = (a + (c ^ (d & (b ^ c))) + 0xA9E3E905); a = ((x << 5) | (x >> (32 - 5))) + b;
  63.             x = (d + (b ^ (c & (a ^ b))) + 0xFCEFA3F8); d = ((x << 9) | (x >> (32 - 9))) + a;
  64.             x = (c + (a ^ (b & (d ^ a))) + 0x676F02D9); c = ((x << 14) | (x >> (32 - 14))) + d;
  65.             x = (b + (d ^ (a & (c ^ d))) + 0x8D2A4C8A); b = ((x << 20) | (x >> (32 - 20))) + c;
  66.             //Раунд 2
  67.             a += ((b ^ c ^ d) + 0xFFFA3942); a = ((a << 4) | (a >> (32 - 4))) + b;
  68.             d += ((a ^ b ^ c) + 0x8771F681); d = ((d << 11) | (d >> (32 - 11))) + a;
  69.             c += ((d ^ a ^ b) + 0x6D9D6122);  c = ((c << 16) | (c >> (32 - 16))) + d;
  70.             b += ((c ^ d ^ a) + 0xFDE5382C); b = ((b << 23) | (b >> (32 - 23))) + c;
  71.             a += ((b ^ c ^ d) + 0xA4BEEAC4); a = ((a << 4) | (a >> (32 - 4))) + b;
  72.             d += ((a ^ b ^ c) + 0x4BDECFA9); d = ((d << 11) | (d >> (32 - 11))) + a;
  73.             c += ((d ^ a ^ b) + 0xF6BB4B60); c = ((c << 16) | (c >> (32 - 16))) + d;
  74.             b += ((c ^ d ^ a) + 0xBEBFBC70); b = ((b << 23) | (b >> (32 - 23))) + c;
  75.             a += ((b ^ c ^ d) + 0x289B7EC6); a = ((a << 4) | (a >> (32 - 4))) + b;
  76.             d += ((a ^ b ^ c) + 0xEAA127FA + key); d = ((d << 11) | (d >> (32 - 11))) + a;
  77.             c += ((d ^ a ^ b) + 0xD4EF3085); c = ((c << 16) | (c >> (32 - 16))) + d;
  78.             b += ((c ^ d ^ a) + 0x04881D05); b = ((b << 23) | (b >> (32 - 23))) + c;
  79.             a += ((b ^ c ^ d) + 0xD9D4D039); a = ((a << 4) | (a >> (32 - 4))) + b;
  80.             d += ((a ^ b ^ c) + 0xE6DB99E5); d = ((d << 11) | (d >> (32 - 11))) + a;
  81.             c += ((d ^ a ^ b) + 0x1FA27CF8); c = ((c << 16) | (c >> (32 - 16))) + d;
  82.             b += ((c ^ d ^ a) + 0xC4AC5665); b = ((b << 23) | (b >> (32 - 23))) + c;
  83.             //Раунд 3
  84.             x = (a + (c ^ (b | ~d)) + 0xF4292244 + key); a = ((x << 6) | (x >> (32 - 6))) + b;
  85.             x = (d + (b ^ (a | ~c)) + 0x432AFF97); d = ((x << 10) | (x >> (32 - 10))) + a;
  86.             x = (c + (a ^ (d | ~b)) + 0xAB9423C7); c = ((x << 15) | (x >> (32 - 15))) + d;
  87.             x = (b + (d ^ (c | ~a)) + 0xFC93A039); b = ((x << 21) | (x >> (32 - 21))) + c;
  88.             x = (a + (c ^ (b | ~d)) + 0x655B59C3); a = ((x << 6) | (x >> (32 - 6))) + b;
  89.             x = (d + (b ^ (a | ~c)) + 0x8F0CCC92); d = ((x << 10) | (x >> (32 - 10))) + a;
  90.             x = (c + (a ^ (d | ~b)) + 0xFFEFF47D); c = ((x << 15) | (x >> (32 - 15))) + d;
  91.             x = (b + (d ^ (c | ~a)) + 0x85845E51); b = ((x << 21) | (x >> (32 - 21))) + c;
  92.             x = (a + (c ^ (b | ~d)) + 0x6FA87E4F); a = ((x << 6) | (x >> (32 - 6))) + b;
  93.             x = (d + (b ^ (a | ~c)) + 0xFE2CE6E0); d = ((x << 10) | (x >> (32 - 10))) + a;
  94.             x = (c + (a ^ (d | ~b)) + 0xA3014314); c = ((x << 15) | (x >> (32 - 15))) + d;
  95.             x = (b + (d ^ (c | ~a)) + 0x4E0811A1); b = ((x << 21) | (x >> (32 - 21))) + c;
  96.             x = (a + (c ^ (b | ~d)) + 0xF7537E82); a = ((x << 6) | (x >> (32 - 6))) + b;
  97.             x = (d + (b ^ (a | ~c)) + 0xBD3AF235); d = ((x << 10) | (x >> (32 - 10))) + a;
  98.             x = (c + (a ^ (d | ~b)) + 0x2AD7D2BB); c = ((x << 15) | (x >> (32 - 15))) + d;
  99.             x = (b + (d ^ (c | ~a)) + 0xEB86D391); b = ((x << 21) | (x >> (32 - 21))) + c;
  100.  
  101.             state[0] = state[0] + a;
  102.             state[1] = state[1] + b;
  103.             state[2] = state[2] + c;
  104.             state[3] = state[3] + d;
  105.  
  106.             //Console.WriteLine("A=" + a.ToString("X8")+" B="+b.ToString("X8")
  107.             //    + " C=" + c.ToString("X8") + " D=" + d.ToString("X8") );
  108.         }
  109.     }
  110.     class Program
  111.     {
  112.         static MFile[] SFiles=new MFile[256];
  113.         static MD5 md5Hash = new MD5CryptoServiceProvider();
  114.         static void Main(string[] args)
  115.         {
  116.             Stage1();
  117.             Stage2();
  118.             //            byte[] hash = new byte[16] {0x10,0x00,0x6A,0xAE,0x11,0x22,0x33,0x44,
  119.             //                                    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00 };
  120.             //            Search(hash);
  121.         }
  122.         static UInt32 Search(byte[] hash)
  123.         {
  124.             const int bufSize=1024*128;
  125.             //            Console.WriteLine(offs.ToString("x9"));
  126.             using (var file = File.OpenRead(@"D:\md5test\_result.bin"))
  127.             {
  128.                 byte[] buf = new byte[bufSize];
  129.                 for(int k=0;k<=0xFF;k++)
  130.                 {
  131.                     hash[0] = (byte)k;
  132.                     long offs = (((long)hash[0] << 24 | (long)hash[1] << 16 | (long)hash[2] << 8 | hash[3]) << 2) - bufSize/2;
  133.                     if (offs < 0) offs = 0;
  134.                     if (offs >= 0x400000000 - bufSize) offs = 0x400000000 - bufSize;
  135.                     file.Position = offs;
  136.                     file.Read(buf, 0, bufSize);
  137.                     byte[] c1 = md5Hash.ComputeHash(buf.SubArray(bufSize-4, 4));
  138.                     Console.Write("\n" + k.ToString("X2") + " 45 6A  : "+c1[2].ToString("X2")+"  ");
  139.                     for (int i = 0; i < 16; i++) Console.Write(c1[i].ToString("X2"));
  140.                 }
  141.             }
  142.             return 0;
  143.         }
  144.         public struct KeyInfo
  145.         {
  146.             public Int32 offs;
  147.             public byte cnt;
  148.             public byte wcnt;
  149.         }
  150.         static void Stage2()
  151.         {
  152.             const int Threads = 4; // Количество потоков сортировки
  153.             long length = new System.IO.FileInfo(@"D:\md5test\00.s1").Length;
  154.             TypeCast buf = new TypeCast();
  155.             TypeCast buf1 = new TypeCast();
  156.             TypeCast tmp;
  157.             buf.Byte = new byte[length + 2048 * 1024];
  158.             buf1.Byte = new byte[length + 2048 * 1024];
  159.             KeyInfo[] KI = new KeyInfo[0x1000000];
  160.             TypeCast oBuf = new TypeCast();
  161.             UInt32[] keys = new UInt32[(length + 2048 * 1024) / 2];
  162.             oBuf.Byte = new byte[(length + 2048 * 1024) / 2];
  163.             var outFile = File.Create(@"D:\md5test\_result.bin");
  164.             Task reader = null, writer = null;
  165.             object[] lock_obj = new object[256]; // Объекты для блокировки сортирующих потоков
  166.             for (int i = 0; i < 256; i++) lock_obj[i] = new object();
  167.             using (var file = File.OpenRead(@"D:\md5test\00.s1"))
  168.             { file.Read(buf.Byte, 0, (int)length); }
  169.  
  170.             for (int f = 0; f <= 255; f++)
  171.             {
  172.                 string path = @"D:\md5test\" + f.ToString("x2") + ".s1";
  173.                 Console.WriteLine(path);
  174.                 length = new System.IO.FileInfo(path).Length;
  175.                 if (f != 0)
  176.                 {
  177.                     //Console.WriteLine("Reader wait"); Console.Out.Flush();
  178.                     reader?.Wait();
  179.                     tmp = buf; buf = buf1; buf1 = tmp;
  180.                     //Console.WriteLine("Readed"); Console.Out.Flush();
  181.                 }
  182.                 if (f != 0xFF)
  183.                 {
  184.                     path = @"D:\md5test\" + (f+1).ToString("x2") + ".s1";
  185.                     var file1 = File.OpenRead(path);
  186.                     reader = file1.ReadAsync(buf1.Byte, 0, (int)new System.IO.FileInfo(path).Length);
  187.                 }
  188.                 int max = (int)length / 8;
  189.                 //Console.WriteLine("Calc counts"); Console.Out.Flush();
  190.                 for (int i = 0; i < max; i++)
  191.                 {
  192.                     uint x=buf.UInt32[i * 2 + 1] = ReverseBytes(buf.UInt32[i * 2 + 1]);
  193.                     KI[x>>8].cnt++;
  194.                 }
  195.                 int sum = 0;
  196.                 //Console.WriteLine("Offsets"); Console.Out.Flush();
  197.                 for (int i = 0; i < 0x1000000; i++)
  198.                 {
  199.                     KI[i].offs = sum;
  200.                     sum += KI[i].cnt;
  201.                 }
  202.                 //Console.WriteLine("Wait writer"); Console.Out.Flush();
  203.                 writer?.Wait();
  204.                 //Console.WriteLine("Sort"); Console.Out.Flush();
  205.                 Task[] tasks = new Task[Threads];
  206.                 int start_val = 0;
  207.                 for (int t = 0; t < Threads; t++)
  208.                     tasks[t] = Task.Run(() =>
  209.                     {
  210.                         int start;
  211.                         lock(tasks)
  212.                         {
  213.                             start = start_val++;
  214.                 //            Console.WriteLine("Thread " + start.ToString() + " started");
  215.                         }
  216.                         for (int i = start; i < max; i+=Threads)
  217.                         {
  218.                             UInt32 ok = buf.UInt32[i * 2 + 1];
  219.                             UInt32 k = ok >> 8;
  220.                             UInt32 v = buf.UInt32[i * 2];
  221.                             int Base = KI[k].offs;
  222.                             if (KI[k].cnt == 1) // Может быть только 1 элемент, коллизии потоков невозможны
  223.                             {
  224.                                 oBuf.UInt32[Base] = v; keys[Base] = ok;
  225.                             }
  226.                             else  // Может быть более одного элемента, понадобится сортировка, возможны коллизии
  227.                             lock(lock_obj[k & 0xFF])
  228.                             {
  229.                                 int maxj = KI[k].wcnt;
  230.                                 if (maxj == 0)
  231.                                 {
  232.                                     oBuf.UInt32[Base] = v; keys[Base] = ok;
  233.                                 }
  234.                                 else
  235.                                 {
  236.                                     int j = 0;
  237.                                     while (
  238.                                             j < maxj &&
  239.                                             (keys[Base + j] < ok ||
  240.                                               (keys[Base + j] == ok && CompareMD5(oBuf.UInt32[Base + j], v) < 0)
  241.                                             )
  242.                                           ) j++;
  243.                                     while (true)
  244.                                     {
  245.                                         UInt32 o_ok = keys[Base + j]; UInt32 o_v = oBuf.UInt32[Base + j];
  246.                                         oBuf.UInt32[Base + j] = v; keys[Base + j] = ok;
  247.                                         if (j >= maxj) break;
  248.                                         v = o_v; ok = o_ok;
  249.                                         j++;
  250.                                     }
  251.                                 }
  252.                                 KI[k].wcnt++;
  253.                             }
  254.                         }
  255.  
  256.                     });
  257.                 Task.WaitAll(tasks);
  258.                 //Console.WriteLine("End sort"); Console.Out.Flush();
  259.                 writer =outFile.WriteAsync(oBuf.Byte, 0, (int)length/2);
  260.                 Array.Clear(KI, 0, KI.Length);
  261.             }
  262.             outFile.Close();
  263.         }
  264.         public static UInt32 ReverseBytes(UInt32 value)
  265.         {
  266.             return (value & 0x000000FFU) << 24 | (value & 0x0000FF00U) << 8 |
  267.                 (value & 0x00FF0000U) >> 8 | (value & 0xFF000000U) >> 24;
  268.         }
  269.         static int CompareMD5(UInt32 v1, UInt32 v2)
  270.         {
  271.             TypeCast c1 = new TypeCast();
  272.             TypeCast c2 = new TypeCast();
  273.             c1.Byte = new byte[16];
  274.             c2.Byte = new byte[16];
  275.             FastMD5.Get2(c1.UInt32, v1);
  276.             FastMD5.Get2(c2.UInt32, v2);
  277.             for (int i=0;i<16;i++)
  278.             {
  279.                 if (c1.Byte[i] == c2.Byte[i]) continue;
  280.                 return (c1.Byte[i] < c2.Byte[i] ? -1 : 1);
  281.             }
  282.             if (v1 != v2) Console.Write("MD5 OF " + v1.ToString() + " and " + v2.ToString() + " IS EQUAL !!!");
  283.             return 0;
  284.         }
  285.         static void Stage1()
  286.         {
  287.             CreateSFiles();
  288.             Console.WriteLine("Stage1 started");
  289.             const int Threads= 5;
  290.             Task[] tasks = new Task[Threads];
  291.             UInt32 start_val = 0;
  292.             for (int i = 0; i < Threads; i++)
  293.                 tasks[i] = Task.Factory.StartNew(() =>
  294.                 {
  295.                     TypeCast hash = new TypeCast();
  296.                     hash.Byte = new byte[16];
  297.                     UInt32 val,start;
  298.                     lock (tasks)
  299.                     {
  300.                         start = val = start_val++;
  301.                         Console.WriteLine("Thread " + val + " started");
  302.                     }
  303.                     do
  304.                     {
  305.                         FastMD5.Get2(hash.UInt32, val);
  306.                         lock (SFiles[hash.Byte[0]])
  307.                         {
  308.                             SFiles[hash.Byte[0]].Add(val, (hash.UInt32[0] >> 8) | (hash.UInt32[1] << 24));
  309.                         }
  310.                         if ((val & 0xFFFFFF) == 0)
  311.                         {
  312.                             Console.WriteLine(val.ToString("x8"));
  313.                             Console.Out.Flush();
  314.                         }
  315.                         val += Threads;
  316.                     } while (val >= Threads /*&& val < 100000000*/);
  317.                     Console.WriteLine("Thread "+start.ToString()+" end at "+val.ToString());
  318.                 });
  319.             Task.WaitAll(tasks);
  320.             for (int i = 0; i <= 255; i++)
  321.             {
  322.                 SFiles[i].Dispose();
  323.                 SFiles[i] = null;
  324.             }
  325.             MFile.freeBuffers();
  326.         }
  327.         static void CreateSFiles()
  328.         {
  329.             for(int i=0;i<=255;i++)
  330.             {
  331.                 Console.WriteLine("Open " + i.ToString());
  332.                 SFiles[i] = new MFile(i);
  333.             }
  334.         }
  335.     }
  336.     [StructLayout(LayoutKind.Explicit, Pack = 2)]
  337.     public class TypeCast
  338.     {
  339.         [FieldOffset(0)]
  340.         public int numberOfBytes;
  341.         [FieldOffset(4)]
  342.         public byte[] Byte;
  343.         [FieldOffset(4)]
  344.         public UInt32[] UInt32;
  345.     }
  346.     public class MFile : IDisposable
  347.     {
  348.         private const int maxBufSize = 262144*2;
  349.         private FileStream file;
  350.         private int num;
  351.         private TypeCast buf;
  352.         private int cur; // Текущая позиция в буфере
  353.         private static ConcurrentBag<TypeCast> freePoll =  new ConcurrentBag<TypeCast>();
  354.         private static Task saveTask=null;
  355.         public MFile(int Num)
  356.         {
  357.             num = Num;
  358.             file=File.Create(@"D:\md5test\" + num.ToString("x2") + ".s1");
  359.             cur = 0;
  360.             CreateBuf();
  361.         }
  362.         private void CreateBuf()
  363.         {
  364.             buf = new TypeCast();
  365.             buf.Byte = new byte[maxBufSize*4];
  366.         }
  367.         public void Add(UInt32 val, UInt32 hash)
  368.         {
  369.             buf.UInt32[cur++] = val; buf.UInt32[cur++] = hash;
  370.             if (cur >= maxBufSize-128*256-(hash>>22)) saveTask=saveBuf();
  371.             return;
  372.         }
  373.         public async Task saveBuf(int len=0)
  374.         {
  375.             saveTask?.Wait();
  376.             if (len == 0) len = cur;
  377.             TypeCast oldBuf;
  378.             oldBuf = buf;
  379.             cur = 0;
  380.             if (!freePoll.TryTake(out buf)) CreateBuf();
  381.             await file.WriteAsync(oldBuf.Byte, 0, len * 4);
  382.             freePoll.Add(oldBuf);
  383.             saveTask = null;
  384.         }
  385.         public void Dispose()
  386.         {
  387.             if (cur != 0) saveTask=saveBuf();
  388.             saveTask?.Wait();
  389.             file.Close();
  390.         }
  391.         public static void freeBuffers()
  392.         {
  393.             TypeCast buf;
  394.             while (freePoll.TryTake(out buf)) ;
  395.         }
  396.     }
  397. }
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!