Как найти определенный байт

Since you mentioned efficiency, here is some heavily optimized C# code I’ve written which uses native addressing and maximal qword-aligned reading to cut the number of memory accesses by a factor of 8. I would be surprised if there is any faster way to scan for a byte in memory in .NET.

This returns the index of the first occurrence of byte ‘v’ within the range of memory starting at offset i (relative to address src), and continuing for length c. Returns -1 if byte v is not found.

// fast IndexOf byte in memory. (To use this with managed byte[] array, see below)
public unsafe static int IndexOfByte(byte* src, byte v, int i, int c)
{
    ulong t;
    byte* p, pEnd;

    for (p = src + i; ((long)p & 7) != 0; c--, p++)
        if (c == 0)
            return -1;
        else if (*p == v)
            return (int)(p - src);

    ulong r = v; r |= r << 8; r |= r << 16; r |= r << 32;

    for (pEnd = p + (c & ~7); p < pEnd; p += 8)
    {
        t = *(ulong*)p ^ r;
        t = (t - 0x0101010101010101) & ~t & 0x8080808080808080;
        if (t != 0)
        {
            t &= (ulong)-(long)t;
            return (int)(p - src) + dbj8[t * 0x07EDD5E59A4E28C2 >> 58];
        }
    }

    for (pEnd += c & 7; p < pEnd; p++)
        if (*p == v)
            return (int)(p - src);

    return -1;
}

Don’t be alarmed by the one multiplication you see; it’s only executed a maximum of once per call of this function in order to do a final deBruijn lookup. The read-only lookup table used for that is a simple shared list of 64 byte values which requires one-time only initialization:

// elsewhere in the static class...

readonly static sbyte[] dbj8 =
{
     7, -1, -1, -1, -1,  5, -1, -1, -1,  4, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1,  6, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1,  3, -1, -1, -1, -1, -1, -1,  1, -1,  2,  0, -1, -1,
};

The -1 values are never accessed and can be left at zero if desired instead, as shown in the following alternative to the preceding table initialization code, if you prefer:

static MyStaticClass()
{
    dbj8 = new sbyte[64];  // initialize the lookup table (alternative to the above)
    dbj8[0x00] = 7;
    dbj8[0x18] = 6;
    dbj8[0x05] = 5;
    dbj8[0x09] = 4;
    dbj8[0x33] = 3;
    dbj8[0x3C] = 2;
    dbj8[0x3A] = 1;
 /* dbj8[0x3D] = 0; */
}

readonly static sbyte[] dbj8, dbj16;

For completeness, here is how to use the function with the method prototype provided by the OP in the original question.

/// Finds the first occurrence of a specific byte in a byte array.
/// If not found, returns -1.
public static unsafe int GetFirstOccurance(byte byteToFind, byte[] byteArray)
{
    fixed (byte* p = byteArray)
        return IndexOfByte(p, byteToFind, 0, byteArray.Length);
}

Discussion
My code is a bit intricate, so detailed examination is left as an exercise for the interested reader. You can study another take on the general approach of gang-wise memory searching in the .NET internal method Buffer.IndexOfByte, but that code has significant drawbacks compared to mine:

• Most significantly, the .NET code only scans 4 bytes at time instead of 8 as in mine.
• It’s a non-public method, so you’d need to use reflection to call it.
• The .NET code has a «performance leak» where the t1 != 0 check gives a false positive, and the four checks that follow are wasted. Note their «fall-through» case: due to this false-positive, they need four final checks—thus allowing fall-through—to maintain correctness, instead of just three.
• The .NET code’s false-positive is caused by an inherently inferior bitwise computation based on overflow of the carry bit from one byte to the next. This leads to two’s complement asymmetries (evidenced by their use of constants 0x7efefeff or 0x81010100) and the occasional «left-wise egress» (i.e., loss) of information regarding the most-significant byte, which is the real problem here. In contrast, I use an underflow computation which keeps each byte’s computation independent of its neighbors’. My method gives a conclusive result in all cases with no false-positive or «fall-through» processing.
• My code uses a branchless technique for the final lookup. A handful of non-branching logical operations (plus one multiplication in this case) is generally believed to favor performance over extended if-else structures, since the latter can disrupt CPU predictive caching. This issue is more important for my 8-byte scanner because without using lookup I’d have twice as many if-else conditions in the final check, as compared to a 4-byte gang-wise scanner.

Of course if you’re not concerned with all this minutiae you can just copy and use the code; I’ve unit-tested it quite exhaustively and verified correct behavior for all well-formed inputs. So while the core functionality is ready to use, you’ll probably want to add argument checking.

[edit:]

String.IndexOf(String s, Char char, int ix_start, int count) ... fast!

Because the above method has worked so successfully in my projects, I extended it to cover 16-bit searching. Here is the same code adapted to search for a 16-bit short, ushort, or char primitive instead of byte. This adapted method was also independently verified against its own respective unit-test methodology adapted from above.

static MyStaticClass()
{
    dbj16 = new sbyte[64];
 /* dbj16[0x3A] = 0; */
    dbj16[0x33] = 1;
    dbj16[0x05] = 2;
    dbj16[0x00] = 3;
}
readonly static sbyte[] dbj16;

public static int IndexOf(ushort* src, ushort v, int i, int c)
{
    ulong t;
    ushort* p, pEnd;

    for (p = src + i; ((long)p & 7) != 0; c--, p++)
        if (c == 0)
            return -1;
        else if (*p == v)
            return (int)(p - src);

    ulong r = ((ulong)v << 16) | v;
    r |= r << 32;

    for (pEnd = p + (c & ~7); p < pEnd; p += 4)
    {
        t = *(ulong*)p ^ r;
        t = (t - 0x0001000100010001) & ~t & 0x8000800080008000;
        if (t != 0)
        {
            i = dbj16[(t & (ulong)-(long)t) * 0x07EDD5E59A4E28C2 >> 58];
            return (int)(p - src) + i;
        }
    }

    for (pEnd += c & 7; p < pEnd; p++)
        if (*p == v)
            return (int)(p - src);

    return -1;
}

And below are the various overloads for accessing this for the remaining 16-bit primitives, plus String (last one shown):

public static int IndexOf(this char[] rg, char v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this char[] rg, char v, int i, int c = -1)
{
    if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
        fixed (char* p = rg)
            return IndexOf((ushort*)p, v, i, c < 0 ? rg.Length - i : c);
    return -1;
}

public static int IndexOf(this short[] rg, short v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this short[] rg, short v, int i, int c = -1)
{
    if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
        fixed (short* p = rg)
            return IndexOf((ushort*)p, (ushort)v, i, c < 0 ? rg.Length - i : c);
    return -1;
}

public static int IndexOf(this ushort[] rg, ushort v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this ushort[] rg, ushort v, int i, int c = -1)
{
    if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
        fixed (ushort* p = rg)
            return IndexOf(p, v, i, c < 0 ? rg.Length - i : c);
    return -1;
}
public static int IndexOf(String s, Char ch, int i = 0, int c = -1)
{
    if (s != null && (c = c < 0 ? s.Length - i : c) > 0)
        fixed (char* p = s)
            return IndexOf((ushort*)p, ch, i, c);
    return -1;
}

Notice that the String overload is not marked as an extension method since this higher-performance replacement version of the function would never be called that way (built-in methods with the same name always take precedence over extension methods). To use it as an extension on String instances, you can change the name of this method. As an example, IndexOf__(this String s,...) would cause it to appear next to the built-in method name in Intellisense listings, perhaps a helpful reminder to opt-in. Otherwise, if you don’t need extension syntax, you can just make sure you call this optimized version directly as a static method of its own class when you want to use it instead of s.IndexOf(Char ch).

Полезняшки от сюда — линк

static class ByteArrayRocks
{

    static readonly int[] Empty = new int[0];

    public static int[] Locate(this byte[] self, byte[] candidate)
    {
        if (IsEmptyLocate(self, candidate))
            return Empty;

        var list = new List<int>();

        for (int i = 0; i < self.Length; i++)
        {
            if (!IsMatch(self, i, candidate))
                continue;

            list.Add(i);
        }

        return list.Count == 0 ? Empty : list.ToArray();
    }

    static bool IsMatch(byte[] array, int position, byte[] candidate)
    {
        if (candidate.Length > (array.Length - position))
            return false;

        for (int i = 0; i < candidate.Length; i++)
            if (array[position + i] != candidate[i])
                return false;

        return true;
    }

    static bool IsEmptyLocate(byte[] array, byte[] candidate)
    {
        return array == null
            || candidate == null
            || array.Length == 0
            || candidate.Length == 0
            || candidate.Length > array.Length;
    }

    static void Main()
    {
        var data = new byte[] { 23, 36, 43, 76, 125, 56, 34, 234, 12, 3, 5, 76, 8, 0, 6, 125, 234, 56, 211, 122, 22, 4, 7, 89, 76, 64, 12, 3, 5, 76, 8, 0, 6, 125 };
        var pattern = new byte[] { 12, 3, 5, 76, 8, 0, 6, 125 };

        foreach (var position in data.Locate(pattern))
            Console.WriteLine(position);
    }
}

Думаю это сильно зависит от того, как часто вам нужно делать поиск в этом файле.
Если не часто — тогда можно просто вычитывать данные порциями, и искать последовательность в них.
Если же очень часто — нужно понять что там за данные и думать как сделать индекс для поиска в этом файле.

Как вариант, можно запустить несколько горутин.
Т.е. пока одна горутина читает одну порцию данных из файла в память — другая ищет в предыдущей порции нужную вам последовательность.

Еще, как вариант, можно сделать простенький индекс (упрощаю, чтобы было легче писать понятный пример)

Допустим у нас есть файл с таким содержимым
0x02 0x09 0x02 0x05 0x09 0x09, 0xf1 0xfa 0x02

Найти нужно последовательность 0x02 0x05

Строим индекс [массив байт от 0x00 до 0xff][слайс адресов этого байта в файле]
т.е.
[значение байта][адрес этого байта в файле1, адрес этого байта в файле2, адрес этого байта в файле3…]
Для указанного файла индекс получится вот такой
[0x00][]
[0x01][]
[0x02][0x00, 0x02, 0x08]
…
[0x05][0x03]
…
[0x09][0x01, 0x04, 0x05]
…
[0xf1][0x06]
…
[0xfa][0x07]
…

Первый байт в искомой последовательности 0x02 0x05 — будет 0x02.
Мы берём слайс в массиве по индексу 0x02 и получаем список адресов где в файле есть 0x02 — [0x00, 0x02, 0x08]
А дальше вы проверяете вашу последовательность только начиная с полученных смещений
Т.е. проверяем следующий байт по адресу 0x00 + 1 == 0x05 (второму символу последовательности) или нет.
Если нет — значит берём след. смещение 0х02 и опять проверяем равен ли след. символ 0x05.
Равен, значит нашли последовательность.

Так как вы упомянули эффективность, вот несколько сильно оптимизированный код С#, который я написал, который использует нативную адресацию и максимальное выравнивание по ключевым словам, чтобы сократить количество обращений к памяти в 8 раз. Я был бы удивлен, если есть какой-либо более быстрый способ сканировать байт в памяти в .NET.

Это возвращает индекс первого вхождения байта ‘v’ в диапазоне памяти, начиная со смещения i (относительно адреса src) и продолжаясь в течение длины c. Возвращает -1, если байт v не найден.

// fast IndexOf byte in memory. (To use this with managed byte[] array, see below)
public unsafe static int IndexOfByte(byte* src, byte v, int i, int c)
{
    ulong t;
    byte* p, pEnd;

    for (p = src + i; ((long)p & 7) != 0; c--, p++)
        if (c == 0)
            return -1;
        else if (*p == v)
            return (int)(p - src);

    ulong r = v; r |= r << 8; r |= r << 16; r |= r << 32;

    for (pEnd = p + (c & ~7); p < pEnd; p += 8)
    {
        t = *(ulong*)p ^ r;
        t = (t - 0x0101010101010101) & ~t & 0x8080808080808080;
        if (t != 0)
        {
            t &= (ulong)-(long)t;
            return (int)(p - src) + dbj8[t * 0x07EDD5E59A4E28C2 >> 58];
        }
    }

    for (pEnd += c & 7; p < pEnd; p++)
        if (*p == v)
            return (int)(p - src);

    return -1;
}

Не пугайтесь одного умножения, которое вы видите; он выполнял только один раз за вызов этой функции, чтобы выполнить окончательный поиск deBruijn. Используемая для этого справочная таблица только для чтения представляет собой простой общий список из 64-байтовых значений, который требует однократной только инициализации:

// elsewhere in the static class...

readonly static sbyte[] dbj8 =
{
     7, -1, -1, -1, -1,  5, -1, -1, -1,  4, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1,  6, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1,  3, -1, -1, -1, -1, -1, -1,  1, -1,  2,  0, -1, -1,
};

К значениям -1 никогда не обращаются, и при желании их можно оставить равными нулю, как показано в следующей альтернативе предыдущему коду инициализации таблицы, если вы предпочитаете:

static MyStaticClass()
{
    dbj8 = new sbyte[64];  // initialize the lookup table (alternative to the above)
    dbj8[0x00] = 7;
    dbj8[0x18] = 6;
    dbj8[0x05] = 5;
    dbj8[0x09] = 4;
    dbj8[0x33] = 3;
    dbj8[0x3C] = 2;
    dbj8[0x3A] = 1;
 /* dbj8[0x3D] = 0; */
}

readonly static sbyte[] dbj8, dbj16;

Для полноты рассмотрим, как использовать функцию с прототипом метода, предоставленным OP в исходном вопросе.

/// Finds the first occurrence of a specific byte in a byte array.
/// If not found, returns -1.
public static unsafe int GetFirstOccurance(byte byteToFind, byte[] byteArray)
{
    fixed (byte* p = byteArray)
        return IndexOfByte(p, byteToFind, 0, byteArray.Length);
}

обсуждение
Мой код немного сложен, поэтому подробное изучение оставлено в качестве упражнения для заинтересованного читателя. Вы можете изучить другой подход к групповому поиску памяти во внутреннем методе .NET Buffer.IndexOfByte, но этот код имеет существенные недостатки по сравнению с моим:

• Что наиболее важно, код .NET сканирует только 4 байта за раз вместо 8, как у меня.
• Это не публичный метод, поэтому вам нужно использовать рефлексию для его вызова.
• В коде .NET есть «утечка производительности», при которой проверка t1 != 0 дает ложное срабатывание, а последующие четыре проверки теряются. Обратите внимание на их «провальный» случай: из-за этого ложноположительного результата им требуется четыре заключительных проверки — таким образом, позволяющих провалиться — для поддержания правильности, а не только три.
• Ложно-положительный код .NET вызван низкоразрядными вычислениями, основанными на переполнении бита переноса от одного байта к следующему. Это приводит к двум асимметриям комплемента (доказанным их использованием констант 0x7efefeff или 0x81010100) и случайным «левосторонним выходом» (т. 0x7efefeff 0x81010100) информации относительно самого 0x81010100 байта, что является настоящей проблемой здесь. В отличие от этого, я использую вычисление нижнего значения, которое сохраняет вычисление каждого байта независимо от его соседей. Мой метод дает убедительный результат во всех случаях без ложноположительной или «сквозной» обработки.
• Мой код использует технику без ветвей для окончательного поиска. Обычно считается, что несколько неразветвленных логических операций (плюс в данном случае одно умножение) способствуют повышению производительности по сравнению с расширенными структурами if-else, поскольку последние могут нарушить прогнозирующее кэширование ЦП. Эта проблема более важна для моего 8-байтового сканера, потому что без использования поиска у меня было бы вдвое if-else условий if-else в окончательной проверке, чем у 4-байтового бандитского сканера.

Конечно, если вас не интересуют все эти мелочи, вы можете просто скопировать и использовать код; Я полностью протестировал его и проверил правильное поведение для всех правильно сформированных входных данных. Таким образом, пока базовая функциональность готова к использованию, вы, вероятно, захотите добавить проверку аргументов.

[редактировать:]

String.IndexOf(String s, Char char, int ix_start, int count) ... fast!

Поскольку вышеупомянутый метод работал так успешно в моих проектах, я расширил его, чтобы охватить 16-битный поиск. Вот тот же код, адаптированный для поиска 16-битного короткого, ushort или char примитива вместо byte. Этот адаптированный метод также был независимо проверен на соответствие его собственной соответствующей методологии модульного теста, адаптированной из вышеописанного.

static MyStaticClass()
{
    dbj16 = new sbyte[64];
 /* dbj16[0x3A] = 0; */
    dbj16[0x33] = 1;
    dbj16[0x05] = 2;
    dbj16[0x00] = 3;
}
readonly static sbyte[] dbj16;

public static int IndexOf(ushort* src, ushort v, int i, int c)
{
    ulong t;
    ushort* p, pEnd;

    for (p = src + i; ((long)p & 7) != 0; c--, p++)
        if (c == 0)
            return -1;
        else if (*p == v)
            return (int)(p - src);

    ulong r = ((ulong)v << 16) | v;
    r |= r << 32;

    for (pEnd = p + (c & ~7); p < pEnd; p += 4)
    {
        t = *(ulong*)p ^ r;
        t = (t - 0x0001000100010001) & ~t & 0x8000800080008000;
        if (t != 0)
        {
            i = dbj16[(t & (ulong)-(long)t) * 0x07EDD5E59A4E28C2 >> 58];
            return (int)(p - src) + i;
        }
    }

    for (pEnd += c & 7; p < pEnd; p++)
        if (*p == v)
            return (int)(p - src);

    return -1;
}

И ниже приведены различные перегрузки для доступа к этому для оставшихся 16-битных примитивов плюс String (последний показан):

public static int IndexOf(this char[] rg, char v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this char[] rg, char v, int i, int c = -1)
{
    if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
        fixed (char* p = rg)
            return IndexOf((ushort*)p, v, i, c < 0 ? rg.Length - i : c);
    return -1;
}

public static int IndexOf(this short[] rg, short v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this short[] rg, short v, int i, int c = -1)
{
    if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
        fixed (short* p = rg)
            return IndexOf((ushort*)p, (ushort)v, i, c < 0 ? rg.Length - i : c);
    return -1;
}

public static int IndexOf(this ushort[] rg, ushort v) => IndexOf(rg, v, 0, rg.Length);
public static int IndexOf(this ushort[] rg, ushort v, int i, int c = -1)
{
    if (rg != null && (c = c < 0 ? rg.Length - i : c) > 0)
        fixed (ushort* p = rg)
            return IndexOf(p, v, i, c < 0 ? rg.Length - i : c);
    return -1;
}
public static int IndexOf(String s, Char ch, int i = 0, int c = -1)
{
    if (s != null && (c = c < 0 ? s.Length - i : c) > 0)
        fixed (char* p = s)
            return IndexOf((ushort*)p, ch, i, c);
    return -1;
}

Обратите внимание, что перегрузка String не помечается как метод расширения, поскольку эта высокопроизводительная замещающая версия функции никогда не будет вызываться таким образом (встроенные методы с одинаковым именем всегда имеют приоритет над методами расширения). Чтобы использовать его как расширение для экземпляров String, вы можете изменить имя этого метода. Например, IndexOf__(this String s,...) заставит его появиться рядом с именем встроенного метода в списках Intellisense, что может быть полезным напоминанием о необходимости подписки. В противном случае, если вам не нужен синтаксис расширения, вы можете просто вызвать эту оптимизированную версию напрямую как статический метод своего собственного класса, если хотите использовать ее вместо s.IndexOf(Char ch).