Битовые поля
From Wiki.conus.info
Немало функций задают различные флаги в аргументах при помощи битовых полей (bit fields). Наверное, вместо этого, можно было бы использовать набор переменных типа bool, но это было бы не очень экономно.
Contents |
Проверка какого-либо бита
Например в win32:
HANDLE fh; fh=CreateFile ("file", GENERIC_WRITE | GENERIC_READ, FILE_SHARE_READ, NULL, OPEN_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL);
Получаем (MSVC 2010):
push 0 push 128 ; 00000080H push 4 push 0 push 1 push -1073741824 ; c0000000H push OFFSET $SG78813 call DWORD PTR __imp__CreateFileA@28 mov DWORD PTR _fh$[ebp], eax
Заглянем в файл WinNT.h:
#define GENERIC_READ (0x80000000L) #define GENERIC_WRITE (0x40000000L) #define GENERIC_EXECUTE (0x20000000L) #define GENERIC_ALL (0x10000000L)
Все ясно, GENERIC_READ | GENERIC_WRITE = 0x80000000 | 0x40000000 = 0xC0000000, что и используется как второй аргумент для CreateFile().
Как CreateFile будет проверять флаги?
Заглянем в KERNEL32.DLL от Windows XP SP3 x86 и найдем в функции CreateFileW в том числе и следующее:
.text:7C83D429 test byte ptr [ebp+dwDesiredAccess+3], 40h .text:7C83D42D mov [ebp+var_8], 1 .text:7C83D434 jz short loc_7C83D417 .text:7C83D436 jmp loc_7C810817
Здесь мы видим инструкцию TEST, она впрочем берет не весь второй аргумент функции, но только его самый старший байт (ebp+dwDesiredAccess+3) и проверяет его на флаги 0x40 (по всей видимости, имеется ввиду GENERIC_WRITE).
TEST это то же что и AND, только без сохранения результата. Логика данного куска кода примерно такая:
if (dwDesiredAccess&0x40000000 == 0) goto loc_7C83D417
Если после операции AND останется этот бит, то флаг ZF не будет поднят и условный переход JZ не сработает. Это возможно только если в переменной dwDesiredAccess присутствует бит 0x40000000. Если его там нет, то эта операция в результате выдаст 0, и в том числе и в флаге ZF и условный переход не сработает.
Попробуем GCC 4.4.1 и Linux:
#include <stdio.h> #include <fcntl.h> void main() { int handle; handle=open ("file", O_RDWR | O_CREAT); };
Получим:
public main main proc near var_20 = dword ptr -20h var_1C = dword ptr -1Ch var_4 = dword ptr -4 push ebp mov ebp, esp and esp, 0FFFFFFF0h sub esp, 20h mov [esp+20h+var_1C], 42h mov [esp+20h+var_20], offset aFile ; "file" call _open mov [esp+20h+var_4], eax leave retn main endp
Заглянем в имплементацию функции open() в библиотеке libc.so.6, но обнаружим что там только вызов сисколла:
.text:000BE69B mov edx, [esp+4+mode] ; mode .text:000BE69F mov ecx, [esp+4+flags] ; flags .text:000BE6A3 mov ebx, [esp+4+filename] ; filename .text:000BE6A7 mov eax, 5 .text:000BE6AC int 80h ; LINUX - sys_open
Значит, битовые поля флагов open будут проверяться уже где-то в ядре.
Разумеется, и стандартные библиотеки Linux и ядро можно получить в виде исходников, но нам интересно попробовать разобраться без них.
Итак, при вызове сисколла sys_open, управление в конечном итоге передается в do_sys_open в ядре Linux 2.6. Оттуда - в do_filp_open(). Эта функция находится в исходниках ядра в fs/namei.c.
Важное отступление. Помимо передачи параметров функции через стек, существует также возможность передавать некоторые из них через регистры. Это называется в том числе fastcall. Это работает немного быстрее, так как процессору не нужно обращаться к памяти, чтобы записать значение в стек и достать его оттуда. В GCC есть опция regparm, и с её помощью можно задать, сколько аргументов можно передать через регистры.
http://www.ohse.de/uwe/articles/gcc-attributes.html#func-regparm
Ядро Linux 2.6 собирается с опцией -mregparm=3:
http://kernelnewbies.org/Linux_2_6_20#head-042c62f290834eb1fe0a1942bbf5bb9a4accbc8f
см. также файл arch\x86\include\asm\calling.h
И для нас это означает, что первые три аргумента функции будут передаваться через регистры EAX, EDX, ECX, затем остальные через стек. Разумеется, если аргументов у функции меньше трех, то будет задействована только часть регистров.
Итак, качаем ядро 2.6.31, собираем его в Ubuntu: make vmlinux, открываем в IDA, находим функцию do_filp_open. В начале мы увидим подобное (комментарии мои):
do_filp_open proc near ... push ebp mov ebp, esp push edi push esi push ebx mov ebx, ecx add ebx, 1 sub esp, 98h mov esi, [ebp+arg_4] ; acc_mode (5th arg) test bl, 3 mov [ebp+var_80], eax ; dfd (1th arg) mov [ebp+var_7C], edx ; pathname (2th arg) mov [ebp+var_78], ecx ; open_flag (3th arg) jnz short loc_C01EF684 mov ebx, ecx ; ebx <- open_flag
GCC сохраняет значения первых трех аргументов в локальном стеке. Иначе, если эти три регистра не трогать вообще, то функции компилятора, распределяющей переменные по регистрам (register allocator), будет очень тесно.
Далее находим примерно такой кусок:
loc_C01EF6B4: ; CODE XREF: do_filp_open+4F�j test bl, 40h ; O_CREAT jnz loc_C01EF810 mov edi, ebx shr edi, 11h xor edi, 1 and edi, 1 test ebx, 10000h jz short loc_C01EF6D3 or edi, 2
0x40 - это то чему равен макров O_CREAT. open_flag проверяется на наличие бита 0x40 и если бит равен нулю, то выполняется следующие за JNZ инструкции.
Установка/сброс бита
Например:
#define IS_SET(flag, bit) ((flag) & (bit)) #define SET_BIT(var, bit) ((var) |= (bit)) #define REMOVE_BIT(var, bit) ((var) &= ~(bit)) int f(int a) { int rt=a; SET_BIT (rt, 0x4000); REMOVE_BIT (rt, 0x200); return rt; };
Имеем в итоге (MSVC 2010):
_rt$ = -4 ; size = 4 _a$ = 8 ; size = 4 _f PROC push ebp mov ebp, esp push ecx mov eax, DWORD PTR _a$[ebp] mov DWORD PTR _rt$[ebp], eax mov ecx, DWORD PTR _rt$[ebp] or ecx, 16384 ; 00004000H mov DWORD PTR _rt$[ebp], ecx mov edx, DWORD PTR _rt$[ebp] and edx, -513 ; fffffdffH mov DWORD PTR _rt$[ebp], edx mov eax, DWORD PTR _rt$[ebp] mov esp, ebp pop ebp ret 0 _f ENDP
Инструкция OR здесь добавляет в переменную еще один бит, игнорируя остальные.
А AND сбрасывает некий бит. Можно также сказать, что AND здесь копирует все биты, кроме одного. Действительно, во втором операнде AND выставлены в еденицу те биты, которые нужно сохранить, кроме одного, который 0. Так проще понять и запомнить.
Если скомпилировать с оптимизацией (/Ox), то будет еще короче:
_a$ = 8 ; size = 4 _f PROC mov eax, DWORD PTR _a$[esp-4] and eax, -513 ; fffffdffH or eax, 16384 ; 00004000H ret 0 _f ENDP
Попробуем GCC 4.4.1 без оптимизации:
public f f proc near var_4 = dword ptr -4 arg_0 = dword ptr 8 push ebp mov ebp, esp sub esp, 10h mov eax, [ebp+arg_0] mov [ebp+var_4], eax or [ebp+var_4], 4000h and [ebp+var_4], 0FFFFFDFFh mov eax, [ebp+var_4] leave retn f endp
Также избыточный код, хотя короче чем у MSVC без оптимизации.
Попробуем теперь GCC с оптимизацией -O3:
public f f proc near arg_0 = dword ptr 8 push ebp mov ebp, esp mov eax, [ebp+arg_0] pop ebp or ah, 40h and ah, 0FDh retn f endp
Уже короче. Важно отметить что через регистр AH, компилятор работает с частью регистра EAX, эта его часть от 8-го до 15-го бита включительно.
Отступление: в 16-битном процессоре 8086 аккумулятор имел название AX и состоял из двух половин, каждая по 8 бит - AL (младшая часть) и AH (старшая). В 80386 регистры были расширены до 32-бит, аккумулятор стал называться EAX, но в целях совместимости, к его "более старым" частям все еще можно обращаться как к AX/AH/AL.
Из-за того что процессоры x86 - все наследники 16-битного 8086, эти старые опкоды короче нежели более новые 32-битные. Иными словами, or ah, 40h занимает 3 байта. Было бы логичнее иметь здесь or eax, 04000h, но это уже 5 байт, или даже 6 (если регистр в первом операнде не EAX).
Если мы скомпилируем этот же пример не только с включенной оптимизацией -O3, но еще и с опцией regparm=3, о которой я писал немного выше, то получится еще короче:
public f f proc near push ebp or ah, 40h mov ebp, esp and ah, 0FDh pop ebp retn f endp
Действительно - первый аргумент уже загружен в EAX, и прямо здесь можно начинать с ним работать. Интересно, что и пролог (push ebp / mov ebp,esp) и эпилог (pop ebp) функции можно выкинуть, но возможно GCC еще не так хорош для подобного. Впрочем, в реальной жизни, подобные короткие функции лучше всего автоматически делать inline:
http://en.wikipedia.org/wiki/Inline_function
Сдвиги
Битовые сдвиги в Си можно делать применяя << и >>.
Вот этот несложный пример иллюстрирует функцию, которая считает количество бит-едениц во входном слове:
#define IS_SET(flag, bit) ((flag) & (bit)) #define SET_BIT(var, bit) ((var) |= (bit)) #define REMOVE_BIT(var, bit) ((var) &= ~(bit)) int f(unsigned int a) { int i; int rt=0; for (i=0; i<32; i++) if (IS_SET (a, 1<<i)) rt++; return rt; };
В этом цикле, i от 0 до 31, а 1<<i будет от 1 до 0x80000000. Описывая это словами, можно сказать "сдвинь еденицу на n бит влево". Т.е., в некотором смысле, выражение 1<<i последовательно выдаст все возможные позиции бит в 32-битном числе. Кстати, освободившийся бит справа всегда обнуляется. Макрос IS_SET проверяет наличие этого бита в a. Макрос на самом деле это операция логического И (AND) и она возвращает ноль если бита там нет, и это же число, если бит там есть. В Си, конструкция if() срабатывает, если выражение внутри её не ноль, пусть хоть 123, поэтому все будет работать.
Компилируем (MSVC 2010):
_rt$ = -8 ; size = 4 _i$ = -4 ; size = 4 _a$ = 8 ; size = 4 _f PROC push ebp mov ebp, esp sub esp, 8 mov DWORD PTR _rt$[ebp], 0 mov DWORD PTR _i$[ebp], 0 jmp SHORT $LN4@f $LN3@f: mov eax, DWORD PTR _i$[ebp] ; i++ add eax, 1 mov DWORD PTR _i$[ebp], eax $LN4@f: cmp DWORD PTR _i$[ebp], 32 ; 00000020H jge SHORT $LN2@f ; цикл закончился? mov edx, 1 mov ecx, DWORD PTR _i$[ebp] shl edx, cl ; edx=edx<<cl and edx, DWORD PTR _a$[ebp] je SHORT $LN1@f ; результат AND был 0? тогда пропускаем следующие команды mov eax, DWORD PTR _rt$[ebp] ; нет, не ноль add eax, 1 ; rt++ mov DWORD PTR _rt$[ebp], eax $LN1@f: jmp SHORT $LN3@f $LN2@f: mov eax, DWORD PTR _rt$[ebp] mov esp, ebp pop ebp ret 0 _f ENDP
Вот так работает SHL (SHift Left).
Скомпилим то же и в GCC 4.4.1:
public f f proc near rt = dword ptr -0Ch i = dword ptr -8 arg_0 = dword ptr 8 push ebp mov ebp, esp push ebx sub esp, 10h mov [ebp+rt], 0 mov [ebp+i], 0 jmp short loc_80483EF loc_80483D0: mov eax, [ebp+i] mov edx, 1 mov ebx, edx mov ecx, eax shl ebx, cl mov eax, ebx and eax, [ebp+arg_0] test eax, eax jz short loc_80483EB add [ebp+rt], 1 loc_80483EB: add [ebp+i], 1 loc_80483EF: cmp [ebp+i], 1Fh jle short loc_80483D0 mov eax, [ebp+rt] add esp, 10h pop ebx pop ebp retn f endp
Инструкции сдвига также активно применяются при делении или умножении на числа-степени двойки (1,2,4,8,etc).
Например:
unsigned int f(unsigned int a) { return a/4; };
Имеем в итоге (MSVC 2010):
_a$ = 8 ; size = 4 _f PROC mov eax, DWORD PTR _a$[esp-4] shr eax, 2 ret 0 _f ENDP
SHR (SHift Right) сдвигает число на 2 бита вправо. При этом освободвиешся два бита слева (т.е., самые старшие разряды) выставляются в нули. А самые младшие 2 бита выкидываются. Фактически, эти два выкинутых бита - это был остаток от деления.
Для того, чтобы это проще понять, представьте себе десятичную систему счисления и число 23. 23 можно разделить на 10 просто выкинув последний разряд (3, это остаток от деления). Останется 2.
Тоже и с умножением. Умножить на 4 это просто сдвинуть число на 2 бита влево, дописав 2 нулевых бита справа (в младших разрядах).
Пример вычисления CRC32
Это распространенный табличный способ вычисления хеша блока алгоритмом CRC32.
Взято тут: http://burtleburtle.net/bob/c/crc.c
/* By Bob Jenkins, (c) 2006, Public Domain */ #include <stdio.h> #include <stddef.h> #include <string.h> typedef unsigned long ub4; typedef unsigned char ub1; static const ub4 crctab[256] = { 0x00000000, 0x77073096, 0xee0e612c, 0x990951ba, 0x076dc419, 0x706af48f, 0xe963a535, 0x9e6495a3, 0x0edb8832, 0x79dcb8a4, 0xe0d5e91e, 0x97d2d988, 0x09b64c2b, 0x7eb17cbd, 0xe7b82d07, 0x90bf1d91, 0x1db71064, 0x6ab020f2, 0xf3b97148, 0x84be41de, 0x1adad47d, 0x6ddde4eb, 0xf4d4b551, 0x83d385c7, 0x136c9856, 0x646ba8c0, 0xfd62f97a, 0x8a65c9ec, 0x14015c4f, 0x63066cd9, 0xfa0f3d63, 0x8d080df5, 0x3b6e20c8, 0x4c69105e, 0xd56041e4, 0xa2677172, 0x3c03e4d1, 0x4b04d447, 0xd20d85fd, 0xa50ab56b, 0x35b5a8fa, 0x42b2986c, 0xdbbbc9d6, 0xacbcf940, 0x32d86ce3, 0x45df5c75, 0xdcd60dcf, 0xabd13d59, 0x26d930ac, 0x51de003a, 0xc8d75180, 0xbfd06116, 0x21b4f4b5, 0x56b3c423, 0xcfba9599, 0xb8bda50f, 0x2802b89e, 0x5f058808, 0xc60cd9b2, 0xb10be924, 0x2f6f7c87, 0x58684c11, 0xc1611dab, 0xb6662d3d, 0x76dc4190, 0x01db7106, 0x98d220bc, 0xefd5102a, 0x71b18589, 0x06b6b51f, 0x9fbfe4a5, 0xe8b8d433, 0x7807c9a2, 0x0f00f934, 0x9609a88e, 0xe10e9818, 0x7f6a0dbb, 0x086d3d2d, 0x91646c97, 0xe6635c01, 0x6b6b51f4, 0x1c6c6162, 0x856530d8, 0xf262004e, 0x6c0695ed, 0x1b01a57b, 0x8208f4c1, 0xf50fc457, 0x65b0d9c6, 0x12b7e950, 0x8bbeb8ea, 0xfcb9887c, 0x62dd1ddf, 0x15da2d49, 0x8cd37cf3, 0xfbd44c65, 0x4db26158, 0x3ab551ce, 0xa3bc0074, 0xd4bb30e2, 0x4adfa541, 0x3dd895d7, 0xa4d1c46d, 0xd3d6f4fb, 0x4369e96a, 0x346ed9fc, 0xad678846, 0xda60b8d0, 0x44042d73, 0x33031de5, 0xaa0a4c5f, 0xdd0d7cc9, 0x5005713c, 0x270241aa, 0xbe0b1010, 0xc90c2086, 0x5768b525, 0x206f85b3, 0xb966d409, 0xce61e49f, 0x5edef90e, 0x29d9c998, 0xb0d09822, 0xc7d7a8b4, 0x59b33d17, 0x2eb40d81, 0xb7bd5c3b, 0xc0ba6cad, 0xedb88320, 0x9abfb3b6, 0x03b6e20c, 0x74b1d29a, 0xead54739, 0x9dd277af, 0x04db2615, 0x73dc1683, 0xe3630b12, 0x94643b84, 0x0d6d6a3e, 0x7a6a5aa8, 0xe40ecf0b, 0x9309ff9d, 0x0a00ae27, 0x7d079eb1, 0xf00f9344, 0x8708a3d2, 0x1e01f268, 0x6906c2fe, 0xf762575d, 0x806567cb, 0x196c3671, 0x6e6b06e7, 0xfed41b76, 0x89d32be0, 0x10da7a5a, 0x67dd4acc, 0xf9b9df6f, 0x8ebeeff9, 0x17b7be43, 0x60b08ed5, 0xd6d6a3e8, 0xa1d1937e, 0x38d8c2c4, 0x4fdff252, 0xd1bb67f1, 0xa6bc5767, 0x3fb506dd, 0x48b2364b, 0xd80d2bda, 0xaf0a1b4c, 0x36034af6, 0x41047a60, 0xdf60efc3, 0xa867df55, 0x316e8eef, 0x4669be79, 0xcb61b38c, 0xbc66831a, 0x256fd2a0, 0x5268e236, 0xcc0c7795, 0xbb0b4703, 0x220216b9, 0x5505262f, 0xc5ba3bbe, 0xb2bd0b28, 0x2bb45a92, 0x5cb36a04, 0xc2d7ffa7, 0xb5d0cf31, 0x2cd99e8b, 0x5bdeae1d, 0x9b64c2b0, 0xec63f226, 0x756aa39c, 0x026d930a, 0x9c0906a9, 0xeb0e363f, 0x72076785, 0x05005713, 0x95bf4a82, 0xe2b87a14, 0x7bb12bae, 0x0cb61b38, 0x92d28e9b, 0xe5d5be0d, 0x7cdcefb7, 0x0bdbdf21, 0x86d3d2d4, 0xf1d4e242, 0x68ddb3f8, 0x1fda836e, 0x81be16cd, 0xf6b9265b, 0x6fb077e1, 0x18b74777, 0x88085ae6, 0xff0f6a70, 0x66063bca, 0x11010b5c, 0x8f659eff, 0xf862ae69, 0x616bffd3, 0x166ccf45, 0xa00ae278, 0xd70dd2ee, 0x4e048354, 0x3903b3c2, 0xa7672661, 0xd06016f7, 0x4969474d, 0x3e6e77db, 0xaed16a4a, 0xd9d65adc, 0x40df0b66, 0x37d83bf0, 0xa9bcae53, 0xdebb9ec5, 0x47b2cf7f, 0x30b5ffe9, 0xbdbdf21c, 0xcabac28a, 0x53b39330, 0x24b4a3a6, 0xbad03605, 0xcdd70693, 0x54de5729, 0x23d967bf, 0xb3667a2e, 0xc4614ab8, 0x5d681b02, 0x2a6f2b94, 0xb40bbe37, 0xc30c8ea1, 0x5a05df1b, 0x2d02ef8d, }; /* how to derive the values in crctab[] from polynomial 0xedb88320 */ void build_table() { ub4 i, j; for (i=0; i<256; ++i) { j = i; j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); j = (j>>1) ^ ((j&1) ? 0xedb88320 : 0); printf("0x%.8lx, ", j); if (i%6 == 5) printf("\n"); } } /* the hash function */ ub4 crc(const void *key, ub4 len, ub4 hash) { ub4 i; const ub1 *k = key; for (hash=len, i=0; i<len; ++i) hash = (hash >> 8) ^ crctab[(hash & 0xff) ^ k[i]]; return hash; } /* To use, try "gcc -O crc.c -o crc; crc < crc.c" */ int main() { char s[1000]; while (gets(s)) printf("%.8lx\n", crc(s, strlen(s), 0)); return 0; }
Нас пока интересует функция crc(). Кстати, обратите внимание, автор указал два инициализатора в выражении for(): hash=len, i=0.
Компилируем с оптимизацией (/Ox). Для краткости, я приведу только функцию crc(), с некоторыми комментариями.
_key$ = 8 ; size = 4 _len$ = 12 ; size = 4 _hash$ = 16 ; size = 4 _crc PROC ; Line 81 mov edx, DWORD PTR _len$[esp-4] xor ecx, ecx ; i будет лежать в регистре ECX mov eax, edx test edx, edx jbe SHORT $LN1@crc push ebx push esi mov esi, DWORD PTR _key$[esp+4] ; ESI = key push edi $LL3@crc: ; Line 82 movzx edi, BYTE PTR [ecx+esi] ; работаем с байтами используя 32-битные регистры. в EDI положим байт с адреса key+i mov ebx, eax ; EBX = (hash = len) and ebx, 255 ; EBX = hash & 0xff xor edi, ebx ; EDI=EDI^EBX - это операциия задействует все 32 бита каждого регистра ; но остальные биты (8-31) будут обнулены всегда, так что все ОК ; они обнулены потому что для EDI это было сделано инструкцией MOVZX выше ; а старшие биты EBX были сброшены инструкцией and ebx, 255 (255 = 0xff) shr eax, 8 ; EAX=EAX>>8; образовавшиеся из ниоткуда биты в результате (биты 24-31) будут заполнены нулями xor eax, DWORD PTR _crctab[edi*4] ; EAX=EAX^crctab[EDI*4] - выбираем элемент из таблицы crctab[] под номером EDI inc ecx ; i++ cmp ecx, edx ; i<len ? jb SHORT $LL3@crc ; да pop edi pop esi pop ebx $LN1@crc: ; Line 84 ret 0 _crc ENDP
Попробуем то же самое в GCC 4.4.1 с опцией -O3:
public crc crc proc near key = dword ptr 8 hash = dword ptr 0Ch push ebp xor edx, edx mov ebp, esp push esi mov esi, [ebp+key] push ebx mov ebx, [ebp+hash] test ebx, ebx mov eax, ebx jz short loc_80484D3 nop ; padding lea esi, [esi+0] ; padding; ESI doesn't changing here loc_80484B8: mov ecx, eax ; save previous state of hash to ecx xor al, [esi+edx] ; al=*(key+i) add edx, 1 ; i++ shr ecx, 8 ; ecx=hash>>8 movzx eax, al ; eax=*(key+i) mov eax, dword ptr ds:crctab[eax*4] ; eax=crctab[eax] xor eax, ecx ; hash=eax^ecx cmp ebx, edx ja short loc_80484B8 loc_80484D3: pop ebx pop esi pop ebp retn crc endp
GCC немного выровнял начало тела цикла по 8-байтной границе, для этого добавил nop и lea esi, [esi+0]
См. также: npad
