SHARE
TWEET

Untitled

a guest Jan 12th, 2018 79 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
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
 
Top