Найти строку символов в двоичных данных

Question

У меня есть двоичный файл, который я загрузил с помощью объекта NSData.Есть ли способ найти последовательность символов, например «abcd», внутри этих двоичных данных и вернуть смещение без преобразования всего файла в строку?Кажется, это должен быть простой ответ, но я не знаю, как это сделать.Есть идеи?

Я делаю это на iOS 3, поэтому у меня нет -rangeOfData:options:range: доступный.

Я собираюсь наградить этой наградой компанию Sixteen Otto за предложение strstr.Я пошел и нашел исходный код функции C strstr и переписал его для работы с байтовым массивом фиксированной длины, который, кстати, отличается от массива символов, поскольку он не завершается нулем.Вот код, который у меня получился:

- (Byte*)offsetOfBytes:(Byte*)bytes inBuffer:(const Byte*)buffer ofLength:(int)len;
{
    Byte *cp = bytes;
    Byte *s1, *s2;

    if ( !*buffer )
        return bytes;

    int i = 0;
    for (i=0; i < len; ++i)
    {
        s1 = cp;
        s2 = (Byte*)buffer;

        while ( *s1 && *s2 && !(*s1-*s2) )
            s1++, s2++;

        if (!*s2)
            return cp;

        cp++;
    }

    return NULL;
}

Это возвращает указатель на первое появление байтов, то, что я ищу в буфере, массив байтов, который должен содержать байты.

Я называю это так:

// data is the NSData object
const Byte *bytes = [data bytes];
Byte* index = [self offsetOfBytes:tag inBuffer:bytes ofLength:[data length]];

Answer 1

Преобразуйте вашу подстроку в NSData объект и искать эти байты в большем NSData с использованием rangeOfData:options:range:.Убедитесь, что кодировки строк совпадают!

На iPhone, где это недоступно, вам, возможно, придется сделать это самостоятельно.Функция С strstr() даст вам указатель на первое появление шаблона в буфере (если ни один из них не содержит нулей!), но не на индекс.Вот функция, которая должен выполните задание (но никаких обещаний, поскольку я еще не пробовал его запускать...):

- (NSUInteger)indexOfData:(NSData*)needle inData:(NSData*)haystack
{
    const void* needleBytes = [needle bytes];
    const void* haystackBytes = [haystack bytes];

    // walk the length of the buffer, looking for a byte that matches the start
    // of the pattern; we can skip (|needle|-1) bytes at the end, since we can't
    // have a match that's shorter than needle itself
    for (NSUInteger i=0; i < [haystack length]-[needle length]+1; i++)
    {
        // walk needle's bytes while they still match the bytes of haystack
        // starting at i; if we walk off the end of needle, we found a match
        NSUInteger j=0;
        while (j < [needle length] && needleBytes[j] == haystackBytes[i+j])
        {
            j++;
        }
        if (j == [needle length])
        {
            return i;
        }
    }
    return NSNotFound;
}

Это выполняется примерно за O(nm), где n — длина буфера, а m — размер подстроки.Он написан для работы с NSData по двум причинам:1) это то, что вы, кажется, имеете в виду, и 2) эти объекты уже инкапсулируют как фактические байты, так и длину буфера.

Answer 2

Если вы используете Snow Leopard, удобным способом будет новый -rangeOfData:options:range:метод в НСдата который возвращает диапазон первого вхождения фрагмента данных.В противном случае вы можете получить доступ к содержимому NSData самостоятельно, используя его метод -bytes для выполнения собственного поиска.

Answer 3

У меня такая же проблема.Я решил это наоборот, по сравнению с предложениями.

сначала я переформатирую данные (предположим, что ваши NSData хранятся в var rawFile) с помощью:

NSString *ascii = [[NSString alloc] initWithData:rawFile encoding:NSAsciiStringEncoding];

Теперь вы можете легко выполнять поиск по строкам, например «abcd» или что-то еще, используя класс NSScanner и передавая строку ascii в сканер.Возможно, это не совсем эффективно, но это работает до тех пор, пока метод -rangeOfData не станет доступен и для iPhone.