Как получить доступ к массиву символов и изменить строчные буквы на прописные, и наоборот

Question

В настоящее время я работаю над проектом класса для Структурированной компьютерной организации с использованием процессора x86. Значение, к которому я обращаюсь, представляет собой 1-байтовый символ, но я не знаю, как сравнить его с заглавными буквами. Они сказали использовать таблицу ASCII в шестнадцатеричном формате, но я не уверен, как их сравнить.

void changeCase (char char_array[], int array_size ) {
    __asm {
            // BEGIN YOUR CODE HERE

        mov eax, char_array;        //eax is base image
        mov edi, 0;

    readArray:
        cmp edi, array_size;
        jge  exit;
        mov ebx, edi;           //using ebx as offset
        shl ebx, 2;
        mov cl, [eax + ebx];    //using ecx to be the storage register

    check:
        //working on it
        cmp cl, 0x41;       //check if cl is <= than ASCII value 65 (A)
        jl next_indx;
        cmp cl, 0x7A;       //check if cl is >= than ASCII value 122 (z)
        jg next_indx;
        cmp cl, 'a';
        jl convert_down;
        jge convert_up;


    convert_down:
        or cl, 0x20;        //make it lowercase
        jmp write;

    convert_up:
        and cl, 0x20;       //make it uppercase
        jmp write;

    write:
        mov byte ptr [eax + ebx], cl    //slight funky town issue here,

    next_indx:
        inc edi;

    exit:
        cmp edi, array_size;
        jl readArray;

    mov char_array, eax;
            // END YOUR CODE HERE
    }
}

На этом этапе все помогает. Заранее спасибо за помощь!

редактировать 1:

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

изменить 2 (+):

Спасибо за полезные глаза людям. Я все еще перевожу все письма сейчас.

Answer 1

Для ясности, я просто использую чистую сборку и предположу, что...

• char_array это 32-битный указатель на [ebp+8],
• array_size является 32-битным числом дополнения до двух в [ebp+12],
• Для вашей платформы (это так для большинства в любом случае), charКодировка ASCII.

Вы должны быть в состоянии вывести это самостоятельно на встроенную сборку. Теперь, если вы посмотрите на стол, который все должны помнить, но вряд ли кто-нибудь узнает, вы заметите некоторые важные детали...

• Заглавные буквы A через Z карта в коды 0x41 через 0x5Aсоответственно.
• Строчные буквы a через z карта в коды 0x61 через 0x7Aсоответственно.
• Все остальное не является буквой, и, следовательно, не нужно преобразовывать регистр.
• Если вы посмотрите на двоичное представление диапазонов прописных и строчных букв, вы заметите, что они абсолютно одинаковы, за исключением того, что заглавные буквы имеют очищенный бит 6, а строчные - его.

В результате алгоритм будет...

while array_size != 0
    byte = *char_array
    if byte >= 0x41 and byte <= 0x5A
        *char_array |= 0x20 // Turn it lowercase
    else if byte >= 0x61 and byte <= 0x7A
        *char_array &= 0xDF // Turn it uppercase
    array_size -= 1
    char_array += 1

Теперь давайте переведем это в сборку...

mov eax, [ebp+8]      # char *eax = char_array
mov ecx, [ebp+12]     # int ecx = array_size

.loop:
    or ecx, ecx       # Compare ecx against itself
    jz .end_loop      # If ecx (array_size) is zero, we're done
    mov dl, [eax]     # Otherwise, store the byte at *eax (*char_array) into `char dl`
    cmp dl, 'A'       # Compare dl (*char_array) against 'A' (lower bound of uppercase letters)
    jb .continue      # If dl` (*char_array) is lesser than `A`, continue the loop
    cmp dl, 'Z'       # Compare dl (*char_array) against 'Z' (upper bound of uppercase letters)
    jbe .is_uppercase # If dl (*char_array) is lesser or equal to 'Z', then jump to .is_uppercase
    cmp dl, 'a'       # Compare dl (*char_array) against 'a' (lower bound of lowercase letters)
    jb .continue      # If dl (*char_array) is lesser than 'a', continue the loop
    cmp dl, 'z'       # Compare dl (*char_array) against 'z' (upper bound of lowercase letters)
    jbe .is_lowercase # If dl (*char_array) is lesser or equal to 'z', then jump to .is_lowercase
    jmp .continue     # All tests failed, so continue the loop

    .is_uppercase:
        or dl, 20h    # Set the 6th bit
        mov [eax], dl # Send the byte back to where it came from
        jmp .continue # Continue the loop

    .is_lowercase:
        and dl, DFh   # Clear the 6th bit
        mov [eax], dl # Send the byte back to where it came from
        jmp .continue # Continue the loop

    .continue:
        inc eax       # Increment `eax` (`char_array`), much of like a pointer increment
        dec ecx       # Decrement `ecx` (`array_size`), so as to match the previous pointer increment
        jmp .loop     # Continue

.end_loop:

Как только код достигает .end_loopГотово.

Я надеюсь, что это пролило свет на вас!

Answer 2

Вариации этого вопроса задают постоянно. Эта версия проблемы (требующая условного поведения сверх всего if(isalpha(c)) c|=0x20;)) сделал проблему достаточно сложной, чтобы сразу было не очевидно, как это сделать эффективно.

Оказывается, что xor не трудно было придумать, и преобразование этого кода в безусловный upcase или downcase требует лишь простого изменения xor 0x20 в and ~0x20 или же or 0x20, (Упрощение немного больше возможно тоже.)

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

Чтение этого ответа, вероятно, будет полезно только после того, как вы поймете основные принципы решения этого с помощью не так оптимизированного кода. OTOH, на самом деле требуется очень мало операций, поэтому кода не так много. И я прокомментировал это сильно. В вики-теге x86 есть много полезных ссылок, от учебных пособий до справочных руководств по настройке производительности.

---

Преобразование между строчными и прописными буквенными символами ASCII требует только установки или очистки 0x20 бит, потому что набор символов ASCII размещается с диапазонами 32 друг от друга и не пересекает границу mod32.

Для каждого байта:

• сделать копию и безоговорочно ИЛИ это с 0x20
• проверьте, если это между 'a' а также 'z'
• если это так, переверните бит регистра ASCII, используя xor и сохранить результат обратно в массив.

Делать ASCII isalpha(3) проверить этот способ безопасно: единственные исходные байты, которые заканчиваются в 'a'.. 'z' диапазон от установки этого бита до прописных буквенных символов. Это просто математика, которая работает для любых двух равных по размеру диапазонов, которые не пересекают %32 граница. (Или %64 граница, если соответствующий бит был 0x40, например).

Чтобы сделать сравнение еще более эффективно, я использую трюк беззнакового сравнения, чтобы в цикле была только одна условная ветвь (кроме самого условия цикла). Смотрите комментарии в коде для объяснения.

/******** Untested. ************/

// ASCII characters are flipped to the opposite case (upper <-> lower)
// non-ASCII characters are left unchanged
void changeCase (char char_array[], int array_size ) {

    __asm{
            // BEGIN YOUR CODE HERE

        mov   esi, char_array;      // MSVC inline asm requires these potentially-redundant copies :(
        mov   ecx, array_size;

        test  ecx,ecx;       // return if(size <= 0)
        jle  early_out;

    next_char:
        mov   al, [esi];     // load the current character
        mov   dl, al;

        // check if the character is alphabetic or not
        // there are two equal-size ranges of characters: one with 0x20 set, and one without
        or    al, 0x20;      // set 0x20 and then just check that lowercase range

        // unsigned compare trick: 0 <= n < high  can be done with one unsigned compare instead of two signed compares
        // low < n < high  can be done by shifting the range first
        sub   al, 'a';       // if al is less than 'a', it will become a large unsigned number
        cmp   al, 'z'-'a';
        ja  non_alpha;      // conditionally skip the flip & store

        xor   dl, 0x20;      // toggle the ASCII case bit
        mov   [esi], dl;
                             // xor [esi], 0x20   // saves the mov earlier, but is otherwise slower
    non_alpha:

        inc   esi;
        dec   ecx;
        jz next_char;

    early_out:
            // END YOUR CODE HERE
    }
}

Этот код мог бы быть более читабельным, если бы некоторые вещи "design doc" находились в блоке вне кода. Это сильно мешает и создает впечатление, что кода много, но на самом деле инструкций очень мало. (Их просто сложно объяснить с помощью коротких комментариев. Код комментирования сложен: слишком очевидные комментарии просто беспорядочные и отнимают время от чтения кода и полезных комментариев.)

---

Векторизованное

На самом деле для x86 я бы использовал SSE или AVX, чтобы сделать 16B за раз, делая тот же алгоритм, но делая сравнение с двумя pcmpgtb, И, конечно же, безусловно сохраняя результаты, поэтому массив всех неалфавитных символов будет по-прежнему загрязнен в кеше, используя большую пропускную способность памяти.

Нет сравнения SSE без знака, но мы все еще можем сместить диапазон, который мы ищем, вниз до дна. Там нет значений меньше, чем -128 так что в подписанном сравнении это работает так 0 делает в без знака сравнения.

Для этого вычтите 128, (или добавить, или xor (без переноса); некуда идти / брать заем). Это может быть сделано в той же операции, что и вычитание 'a',

Затем используйте результат сравнения в качестве маски для обнуления байтов в векторе 0x20, так что только буквенные символы получают XOR с 0x20. (0 - это элемент идентификации для XOR / add / sub, который часто очень удобен для условных выражений SIMD).

Смотрите также strtoupper версия, которая была протестирована, и код для вызова ее в цикле, включая обработку входных данных, не кратных 16, для строк C неявной длины (поиск завершающего 0 на лету).

#include <immintrin.h>

// Call this function in a loop, with scalar cleanup.  (Not implemented, since it's the same as any other vector loop.)

// Flip the case of all alphabetic ASCII bytes in src
__m128i inline flipcase(__m128i src) {
    // subtract 'a'+128, so the alphabetic characters range from -128 to -128+25 (-128+'z'-'a')
    // note that adding 128 and subtracting 128 are the same thing for 8bit integers.
    // There's nowhere for the carry to go, so it's just xor (carryless add), flipping the high bit

    __m128i lcase = _mm_or_si128(src, _mm_set1_epi8(0x20));

    __m128i rangeshift= _mm_sub_epi8(lcase, _mm_set1_epi8('a'+128));
    __m128i non_alpha = _mm_cmpgt_epi8(rangeshift, _mm_set1_epi8(-128 + 25));  // 0:alphabetic   -1:non-alphabetic

    __m128i flip  = _mm_andnot_si128(non_alpha, _mm_set1_epi8(0x20));       // 0x20:alpha    0:non-alpha

    return          _mm_xor_si128(src, flip);
    // just mask the XOR-mask so non-alphabetic elements are XORed with 0 instead of 0x20
    // XOR's identity value is 0, same as for addition
}

Это компилируется в хороший код, даже без AVX, только с одним дополнительным movdqa сохранить копию реестра. Смотрите ссылку на Godbolt для двух более ранних версий (одна использует два сравнения для простоты, другая использует pblendvb прежде чем я вспомнил, чтобы замаскировать вектор 0x20 с вместо результата.)

flipcase:
        movdqa  xmm2, XMMWORD PTR .LC0[rip]    ; 0x20
        movdqa  xmm1, xmm0
        por     xmm1, xmm2
        psubb   xmm1, XMMWORD PTR .LC1[rip]    ; -31
        pcmpgtb xmm1, XMMWORD PTR .LC2[rip]    ; -103
        pandn   xmm1, xmm2
        pxor    xmm0, xmm1
        ret

section .rodata
    .LC0:   times 16 db  32
    .LC1:   times 16 db  -31
    .LC2:   times 16 db  -103

---

Эта же идея использования теста без ответвлений также будет работать для байтового цикла:

        mov   esi, char_array;
        mov   ecx, array_size;

        test  ecx,ecx;       // return if(size <= 0)
        jle  .early_out;

    ALIGN 16   ; really only need align 8 here, since the next 4 instructions are all 2 bytes each (because op  al, imm8  insns have a special encoding)
    .next_char:
        mov   al, [esi];     // load the current character
        mov   dl, al;

        // check if the character is alphabetic or not
        or    al, 0x20;        
        sub   al, 'a';
        cmp   al, 'z'-'a';   // unsigned compare trick: 'a' <= al <= 'z'
        setna al;            // 0:non-alpha  1:alpha  (not above)
        shl   al, 5;         // 0:non-alpha  0x20:alpha
        xor   dl, al;        // conditionally toggle the ASCII case bit
        mov   [esi], dl;     // unconditionally store

        inc   esi;
        dec   ecx;           // for AMD CPUs, or older Intel, it would be better to compare esi against an end pointer, since cmp/jz can fuse but dec can't.  This saves an add ecx, esi outside the loop
        jz .next_char;
    .early_out:

Для 64-битного кода, просто используйте rsi вместо esi, Все остальное тоже самое.

Судя по всему встроенный asm MSVC не позволяет .label имена локальных символов. Я поменял их для первой версии (с условной веткой), но не для этой.

С помощью movzx eax, byte [esi] может быть немного лучше на некоторых процессорах, чтобы избежать ложной зависимости от значения eax при входе в функцию. OTOH, только AMD имеет эту проблему (и Silvermont), но movzx не так дешево, как нагрузка на AMD. (Это на Intel; один моп, который использует только порт загрузки, а не порт ALU). Работает на al после этого все еще хорошо, так как он избегает частичного останова регистрации (или дополнительных инструкций, чтобы избежать этого) от чтения eax после setcc пишет al, (Здесь нет setcc r/m32, только r/m8, к несчастью).

---

Мне интересно, что бы подумал профессор, если бы кто-нибудь сдал такой код для такого задания.: Я сомневаюсь, что даже умный компилятор использовал бы это setcc / shift трюк, если вы не привели компилятор к нему. (Может быть unsigned mask = (tmp>='a' && tmp<='z'); mask <<= 5; a[i] ^= mask; или что-то в этом роде. Компиляторы знают об уловке сравнения без знака, но в некоторых случаях gcc не использует его для проверки диапазона, не зависящего от времени компиляции, даже когда он может доказать, что диапазон достаточно мал.

Answer 3

В ASCII 'a'-'z' и 'A'-'Z' эквивалентны, кроме одного бита, 0x20

твой друг здесь XOR.

если у вас есть символ ("A" - "Z" или "a" - "z"), XOR с 0x20 переключит регистр;

перед XORing, проверка диапазона имеет смысл. (чтобы увидеть, является ли значение действительно буквой)
Вы можете упростить эту проверку диапазона, ORing значение, чтобы проверить с 0xef, который сделает 'a' в 'A' и 'z' в 'Z', а затем выполнить проверку диапазона только один раз
(если вы сравните только с <'a' и>'Z', вы пропустите символы между ними ('[', ']' и т. д.)

Answer 4

В таблице ASCII все буквы являются непрерывными:

A=0x41=01000001
a=0x61=01100001

Z=0x5A=01011010
z=0x7A=01111010

Таким образом, вы можете видеть, что переключая 6-й бит, вы преобразуете верхний регистр в нижний регистр.

Answer 5

Благодаря @KemyLand за полезную разбивку кода на ассемблере я выяснил, как преобразовать заглавные буквы в строчные и наоборот.

void changeCase (char char_array[], int array_size ) {
     //this function is designed to change lowercase letters to uppercase, and vice-versa, from a char-array given the array and its size.
__asm{
        // BEGIN YOUR CODE HERE

    mov eax, [ebp + 8];     //move to register value parameter 1 (the array)
    mov ecx, [ebp + 12];    //likewise parameter 2 (the array size)

    START:

        or ecx, ecx;    //check if pointer is 0
        cmp ecx, 0;
        je endloop;   //go to end loop

        mov dl,byte ptr [eax];  //not sure if needed, but reassurance
        cmp dl, 0x41;   // is char an A?
        jl cont;

        cmp dl, 0x5A;   // is char a Z?
        jle convertUP;

        cmp dl, 0x61;   // is char an a?
        jl cont;

        cmp dl, 0x7A;   // is char a z?
        jle convertDOWN;

        jmp cont;


    convertUP:
        or dl, 0x20;        //Yes! Finally got it working!
        mov byte ptr [eax], dl;

        jmp cont;

    convertDOWN:
        and dl, 0xdf;       //this will work for sure.
        mov[eax], dl;

        jmp cont


    cont:
        inc eax;
        dec ecx;

        jmp START;

    endloop:
}

}

Не стесняйтесь помочь объяснить, что я мог пропустить! Спасибо всем за то, что помогли мне лучше понять процессор сборки x86.