Graph visualization in DOT / Визуализация графов в языке DOT

The English version of the post is below.

---

Предыстория. Мы обрабатываем финансовые транзакции. Возникла задача профилирования. Решили записать путь прохода транзакции по системе и построить граф связей между модулями - кто кого вызывает. Два способа построения: на основе статического анализа исходников и через трассировку реальных вызовов во время выполнения.

Итак, связи зафиксированы. Теперь их надо их как-то представить и построить граф, визуально.

Вроде не самая тривиальная задача, но оказывается, решается весьма просто.

Есть такой язык представления графов, называется DOT. Прелесть его в предельной простоте. Например, простейший граф:

graph name {
  a -- b
  b -- c
  b -- d
}

Натравливаешь на это дело специальную программу и получаешь:


Все! Картинка на выходе в SVG. Можно хоть на стену вешать.

К сожалению, лучший софт, что я нашел для визуализации DOT - это Graphviz. Вроде и работает неплохо, строя весьма большие графы, и есть на всех платформах, благодаря Java, но по интерфейсу - это запредельный и неописуемый кусок говна. Увы.

Если кому интересно, я выложил пример реальной трассировки (по понятным причинам, имена изменены). В целом дает представление о простоте исходника и о возможностях визуализации - PNG и SVG.

Повторюсь - процесс формализации графа крайне прост - нужно только задать пары связанных вершин. Можно делать направленные графы, можно задавать вершинам и дугам разные атрибуты.

В целом, отличная технология.

---

Background. We do financial transactions processing. At some point we decided that we need profiling. We could record a path of how a transaction being passed amongst modules. There are two options - either to do static analysis or to trace the runtime.

So, the connections are determined and now we have to formalize and visualize them.

At the first glance this is not an easy task, but it turned out there is a simple and elegant solution.

There is a plain text language to declare graphs -- DOT. Its beauty is in ultimate simplicity. For example, a trivial graph:

graph name {
  a -- b
  b -- c
  b -- d
}

Feed it to special software and get this:


That's it! The output is in SVG, ready to stick on a wall.

Unfortunately, the best software I've found to visualize DOT is Graphviz. It does pretty decent job properly processing quite sophisticated graphs, but in terms of user experience it is shite.

If anyone is interested, I've uploaded a real trace (obviously, names are obfuscated). It gives an idea about simplicity of the source and visualization capabilities - PNG and SVG.

Again, the graph formalization is dead simple - you only need to specify pairs of connected vertices. Also, in DOT you can describe directed graphs and extra attributes of the vertices.

To sum up, great technology.

Stuck process detector / Монитор зависших процессов

The english version of the post is below.

————————

Есть задача - нужна утилита для обнаружения зависших или заблокированных долгоиграющих серверных процессов. Если процесс «завис» - это значит, либо он торчит в deadlock’e, либо крутится в бесконечном цикле.

Пока есть вот такая идея - для каждого процесса, находящегося под контролем, периодически делать извне снимок стeка. Например:

#0  0x991a8c22 in mach_msg_trap ()
#1  0x991a81f6 in mach_msg ()
#2  0x968870ea in __CFRunLoopServiceMachPort ()
#3  0x96890214 in __CFRunLoopRun ()
#4  0x9688f8ec in CFRunLoopRunSpecific ()
#5  0x9688f798 in CFRunLoopRunInMode ()
#6  0x92158a7f in RunCurrentEventLoopInMode ()
#7  0x9215fd9b in ReceiveNextEventCommon ()
#8  0x9215fc0a in BlockUntilNextEventMatchingListInMode ()
#9  0x90010040 in _DPSNextEvent ()
#10 0x9000f8ab in -[NSApplication nextEventMatchingMask:untilDate:inMode:dequeue:] ()
#11 0x9000bc22 in -[NSApplication run] ()
#12 0x902a018a in NSApplicationMain ()
#13 0x0012e356 in main ()

Для Linux, HPUX и Solaris есть команда pstack, для AIX - procstack. Уверен, что и для Windows можно подобное замутить. Process Explorer это умеет делать, значит можно сделать и программно.

Сравнивая текущий снимок с предыдущим, можно понять, насколько он изменился. Если он вообще не изменился или изменился только по некоторым начальным функциям (например, внутри ядра), то можно предположить, что процесс «завис». Случай deadlock’а на файле или базе данных еще проще, так как программа просто будет постоянно торчать на одной функции внутри ядра.

Понятно, что сравнение стеков должно все-таки учитывать особенности проверяемых процессов. Можно сделать его конфигурируемым, например, через регулярные выражения или скриптовой язык типа Lua.

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

Может я изобретаю велосипед?

—————————

There is a problem — how to automatically detect stuck long running server processes? Say if a process is stuck it means there is a deadlock or it is spinning in an infinite loop.

An idea — periodically take a snapshot of the process stack trace. For instance:

#0  0x991a8c22 in mach_msg_trap ()
#1  0x991a81f6 in mach_msg ()
#2  0x968870ea in __CFRunLoopServiceMachPort ()
#3  0x96890214 in __CFRunLoopRun ()
#4  0x9688f8ec in CFRunLoopRunSpecific ()
#5  0x9688f798 in CFRunLoopRunInMode ()
#6  0x92158a7f in RunCurrentEventLoopInMode ()
#7  0x9215fd9b in ReceiveNextEventCommon ()
#8  0x9215fc0a in BlockUntilNextEventMatchingListInMode ()
#9  0x90010040 in _DPSNextEvent ()
#10 0x9000f8ab in -[NSApplication nextEventMatchingMask:untilDate:inMode:dequeue:] ()
#11 0x9000bc22 in -[NSApplication run] ()
#12 0x902a018a in NSApplicationMain ()
#13 0x0012e356 in main ()

For Linux, HPUX and Solaris there is a tool called pstack, and procstack on AIX. I’m sure it is possible to do the same on Windows because Process Explorer can do it.

Comparing the current stack trace with the previous one we can measure how much it has been changed. If the stack wasn’t changed at all or only a few deepest lines were changed (for example, inside the kernel), we may assume that this process is stuck. The deadlock on a file or database is even simpler because the code will be blocked on a function inside the kernel.

Of course, such detector has to be adjusted for specifics of the monitored processes. But it can be configurable via regular expressions or a script language as Lua, for instance.

The good thing is that such monitor doesn’t require any changes in the target software, and can be implemented on any language suitable for easy text parsing, for example, Ruby or Python.

Am I reinventing a wheel?

Виртуальные private-функции в C++ / Virtual private functions in C++

Note: This post is in two languages. The English one is the second.

---

Наткнулся на интересный, как мне показалось, код. Там использовалась виртуальная private функция. Прием немного странный, но сейчас не об этом.

Сначала мне показалось, что такой код не должен компилироваться, так как если функция private, она недоступна для использования в дочерних классах. Наблюдался какой-то очередной пробел в моих знаниях по C++.

Я написал программу:

#include <iostream>

class A {
public:
  void bar() { foo(); }
private:
  virtual void foo() = 0;
};

class B: public A {
private:
  virtual void foo() { std::cout << "B::foo()" << std::endl; }
};

int main(int argc, char* argv[]) {
  A* a = new B();
  a->bar();
  delete a;
  return 0;
}

И VS2010 и GCC прекрасно его съели, и программа печатает "B::foo()".

Напрашивание такое объяснение - механизм виртуальных функций (технически переопределение функций через vtable) - это runtime, а public/private - это compile time. Получается, что в compile time все законно, и разделение на private/protected/public не зависит от виртуальности функции, а в runtime класс B просто подставляет другую функцию через vtable уже вне зависимости от private/public.

---

I have come across an interesting in my point of view bit of code. There was a virtual private function. The approach is odd at the first place and I thought it shouldn't even compile, but surprisingly it did. I felt that this was yet another gap in my C++.

I wrote this code:

#include <iostream>

class A {
public:
  void bar() { foo(); }
private:
  virtual void foo() = 0;
};

class B: public A {
private:
  virtual void foo() { std::cout << "B::foo()" << std::endl; }
};

int main(int argc, char* argv[]) {
  A* a = new B();
  a->bar();
  delete a;
  return 0;
}

VS2010 and GCC compile it perfectly and it prints out "B::foo()".

I have concluded that the virtual function mechanism usually implemented via vtable is runtime, but public/private is compile time, and they don't depend on each other.

Тонкости использования getenv() и putenv()

Нарвался тут на интересные грабли с функциями getenv() и putenv().

С putenv() у меня уже был интересный опыт.

Часто люди пишут так:

if (getenv("A_FLAG")) {
  ...
}

Это работает неплохо для переменных-флагов, которые либо есть, либо нет. Значение не важно.

Что получилось у меня:

int main(...) {
  putenv("GLOBAL_FLAG=1");  // Глобальное значение для всей программы.
  ...
  system("xyz");            // Это программа должна видеть GLOBAL_FLAG=1.
  ...
  do_stuff();
  ...
}

void do_stuff() {
  ...
  if (something) {
    putenv("GLOBAL_FLAG="); // Убрать переменную.
    system("abc");          // А вот для этой программы флаг должен быть убран.
    ...
  }
  ...
  if (getenv("GLOBAL_FLAG") {
     // И вот тут начиналась ерунда на разных платформах.
  }
}

А корень зла тут в том, что после putenv() результат getenv() может стать либо NULL, либо "", в зависимости от платформы.

Например:

if (getenv("GLOBAL_FLAG") {

работает только на Windows и правильнее писать:

const char* p = getenv("GLOBAL_FLAG");
if (p != NULL && *p != '\0') {
  ...
}

И лучше сделать wrapper для getenv():

std::string GetEnv(const char* name) {
  const char* v = getenv(name);
  return v ? v : "";
}

И для проверки писать:

if (!GetEnv("var").empty()) {
  ..
}

Для теста я написал программу, которая выставляет переменную и проверяет ее значение через getenv() и через вызов дочерней программы.

#include <string>
#include <vector>
#include <iostream>
#include <cstdlib>

#ifdef WINDOWS
#define putenv _putenv
#endif

void PrintVariableViaShell(const std::string& name) {
  std::cout << "Value from shell:" << std::endl;
  const std::string cmd =
#ifdef WINDOWS
    std::string("cmd /c echo [%") + name + "%]";
#else
    std::string("/bin/sh -c \"echo [$") + name + "]\"";
#endif
  std::cout << cmd << std::endl;
  std::system(cmd.c_str());
}

void PrintVariableViaGetEnv(const std::string& name) {
  std::cout << "Value from getenv():" << std::endl;
  const char* v = std::getenv(name.c_str());
  std::cout << "[" << (v ? v : "<NULL>") << "]" << std::endl;
}

void SetVariableDeleteAndPrint(const char* name_value, const bool equ) {
  const std::string& name_value_s(name_value);
  const std::string name = name_value_s.substr(0, name_value_s.find('='));

  putenv(const_cast<char*>(name_value));
  std::vector<char> delete_without_equ(name.begin(), name.end());
  delete_without_equ.push_back('\0');
  putenv(&delete_without_equ[0]);

  std::cout << "Value after deleting WITHOUT '=':" << std::endl;
  PrintVariableViaShell(name);
  PrintVariableViaGetEnv(name);

  std::cout << std::endl;

  putenv(const_cast<char*>(name_value));
  std::vector<char> delete_with_equ(name.begin(), name.end());
  delete_with_equ.push_back('=');
  delete_with_equ.push_back('\0');
  putenv(&delete_with_equ[0]);

  std::cout << "Value after deleting WITH '=': " << std::endl;
  PrintVariableViaShell(name);
  PrintVariableViaGetEnv(name);
}

int main(int argc, char* argv[]) {
#ifdef WINDOWS
  std::cout << "WINDOWS" << std::endl;
#else
  system("uname");
#endif
  SetVariableDeleteAndPrint("ABC=123", true);
  return 0;
}

И вот результы с разных платформ.

Linux

Linux
Value after deleting WITHOUT '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[]
Value from getenv():
[<NULL>]

Value after deleting WITH '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[]
Value from getenv():
[]

AIX

AIX
Value after deleting WITHOUT '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[123]
Value from getenv():
[123]

Value after deleting WITH '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[]
Value from getenv():
[]

SunOS

SunOS
Value after deleting WITHOUT '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[123]
Value from getenv():
[123]

Value after deleting WITH '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[]
Value from getenv():
[]

HP-UX

HP-UX
Value after deleting WITHOUT '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[123]
Value from getenv():
[123]

Value after deleting WITH '=':
Value from shell:
/bin/sh -c "echo [$ABC]"
[]
Value from getenv():
[]

WINDOWS

WINDOWS
Value after deleting WITHOUT '=':
Value from shell:
cmd /c echo [%ABC%]
[123]
Value from getenv():
[123]

Value after deleting WITH '=':
Value from shell:
cmd /c echo [%ABC%]
[%ABC%]
Value from getenv():
[<NULL>]

Только на Windows getenv() возвращает NULL после удаления. На остальных это будет пустая строка.

Забавно, на Linux можно удалять переменные через putenv("name") (без знака "="), а тогда getenv() будет возвращать NULL.

Посты по теме:

• Статический аргумент функции putenv()

Закомментированные куски кода

Закомментированные куски кода - зло, если они не являются частью документации. Увы, не всегда удается найти достаточно слов, чтобы убедить людей довериться репозиторию и таки удалить комментированный код, который "может мне скоро понадобится". Вот тут на помощь приходят цитаты из книг. Почему-то люди больше верят напечатенному на бумаге, особенно в книге, особенно от популярного издательства.

Ребята купили в офис "Test Driven Development for Embedded C" от James W. Grenning.

Хоть там и много про hardware, но примеры как можно и нужно изолировать зависимости для упрощения тестирования на языке С очень полезные. Кроме того описаны пара xUnit библиотек для этого языка (хотя cmockery нет).

Итак, цитата (как есть, без сокращении и перевода).

Commented-out Code

Sources files littered with commented-out code are an ugly mess. New or returning programmers are faced with questions about what the code is supposed to do. "Should the code be uncommented?" "It is no longer needed?" "When will it be needed and under what circumstances is it needed?" "What's that for?"

The solution to this code smell is simple; delete the commented-out code. It can always be recovered from your source repository.

Посты по теме:

• Unit-тестирование в языке С

strcpy() для перекрывающихся строк

Рассмотрим программу:

#include <string.h>
#include <stdio.h>

int main(int argc, char* argv[]) {
  char b[32];
  strcpy(b, "123456789012345");
  strcpy(b + 1, b);
  printf("[%s]\n", b);
  return 0;
}

Тут ясно видна проблема - строки, передаваемые в strcpy(), перекрываются.

По-хорошему, тут имеется неопределенное поведение, так как strcpy() не гарантирует порядок перемещения байт, а именно от него зависит в данном случае результат.

Проверим на разных компиляторах и платформах.

Visual Studio 2010 64-bit

[1123446788012245]

Строка искажается каждые четыре байта, явно копировали по 32 бита.

Linux 64-bit

[1123456788012345]

Уже иной результат. Компилятор и libc:

ldd --version
ldd (GNU libc) 2.5

gcc --version
gcc (GCC) 4.1.2 20080704 (Red Hat 4.1.2-50)

В "man strcpy" говорят:

The strings may not overlap...

Странно, почему не "must not".

Solaris (SPARC)

[1123446788012245]

Компилятор и libc:

cc -V
cc: Sun C 5.8 2005/10/13

version /usr/lib/libC*
version of "/usr/lib/libC.so.3": SC2.0.1 12/20/94 Sun C++ 3.0.1 patch 100962-09
version of "/usr/lib/libC.so.5": Sun SUNWlibC SunOS 5.10 Patch 119963-06 2006/04/21
version of "/usr/lib/libCrun.so.1": Sun SUNWlibC SunOS 5.10 Patch 119963-06 2006/04/21
version of "/usr/lib/libCstd.so.1": Sun SUNWlibC SunOS 5.10 Patch 119963-06 2006/04/21

AIX

[1111111111012245]

Тут результат явно левый. Но зато в документации сказано ясно и понятно:

String movement is performed on a character-by-character basis and starts at the left. Overlapping moves toward the left work as expected, but overlapping moves to the right may give unexpected results.

Компилятор и libc:

lslpp -L | grep Compiler
vacpp.cmp.core            8.0.0.20    C     F    IBM XL C/C++ Compiler

lslpp -L | grep libc
bos.rte.libc               5.3.9.1    C     F    libc Library

HP-UX

[1123456789012345]

Компилятор:

what `which cc`

HP C/aC++ for Integrity Servers B3910B A.06.22 [Nov 14 2008]

Вроде скопировано правильно, но в документации (man strcpy) говорят (формулировка интересна):

Character movement is performed differently in different implementations, so moves involving overlapping source and destination strings may yield surprises.

Вывод: strcpy() - нехорошая функция, по многим причинам.

Код возврата процесса в случае его падения

Был интересный баг - в процессе выполнения скрипта сборки выполнение тестов приводило к жесткому падению процесса. Там был какой-то явный баг с памятью. Но самое интересное дальше. Makefile после падения процесса, выполняющего тесты, продолжал работать, что означало завершение упавшего процесса с нулевым кодом, а должно было быть что-то явно ненулевое.

С багом мы разобрались (включая проблему в Makefile), но возник у меня общий вопрос: с каким именно кодом завершается процесс, если он упал, не успев выполнить exit().

В UNIXах есть специальные макросы, которыми можно проинспектировать код возврата wait(). Но, все UNIXы разные, и к тому же есть еще Windows.

В итоге я написал небольшую самопадающую программу:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main(int argc, char* argv[]) {
  char cmd[80];
  int r;
  sprintf(cmd, "%s ?", argv[0]);
  if (argc > 1) {
    if (argv[1][strlen(argv[1]) - 1] == '1')
      *(char *)0 = 0;
    exit(0x77);
  }
  printf("Normal: %08X\n", system(cmd));
  cmd[strlen(cmd) - 1] = '1';
  printf("Crash : %08X\n", system(cmd));
  return 0;
}

И запустил на некоторых характерных машинах.

Windows 7, Visual Studio 2010, "cl crash.c && crash":

Normal: 00000077
Crash : C0000005

Linux x86_64 ("cс -o crash crash.c && ./crash"):

Normal: 00007700
Crash : 0000000B

Сигнал 0x0B (13) - это, кстати, SIGSEGV, segmentation violation, что, собственно, и произошло.

Solaris SPARC 5.10:

Normal: 00007700
Segmentation Fault - core dumped
Crash : 00008B00

HP-UX Itanium 2:

Normal: 00007700
sh: 25112 Memory fault(coredump)
Crash : 00008B00

AIX 5.2:

Normal: 00007700
Crash : FFFFFFFF

Тут, видимо, до system() код возврата не дошел совсем.

Вывод: все крайне зависит (как всегда) от операционной системы.

Скрипты на Lua в С++, версия 2

В прошлом году я писал мою микро библиотеку для встраивания Lua как скриптового языка в программы на С++.

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

Недавно Alexei Bezborodov вдохнул в проект новую жизнь, исправив несколько ошибок и, самое главное, выпустив новую версию.

Его ветка теперь является основной, а старая оставлена для истории.

Ниже анонс от Алексея.

---

Напишу здесь последние новости для интересующихся.

Появилась новая версия 0.1.0.

В ней добавлено:

• Новый тип LuaScript::Double_LuaArg
• Полноценный вектор LuaScript::Vector_LuaArg
• Нестатические функции. Возможность передавать в функцию локальные объекты.
• Новое описание.

Рекомендую посмотреть тесты. В них есть пример работы с двухмерным вектором и другие полезности.

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

---

Информация по теме:

• Скрипты на Lua в С++
• Lua C++ Wrapper

Кто из компиляторов быстрее - cl, lcc или tcc

Люблю делать всякие сравнения компиляторов.

Сегодня на ринге Студия 2010, lcc и tcc. Все три я активно использую под Windows для языка С.

Сравнивать будем на любимом решете Эратосфена (erato-c-int.c):

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <string.h>
#include <math.h>

int main(int argc, char* argv[]) {
  int n = argc > 1 ? atoi(argv[1]) : 100;
  int* S;
  int count;
  int sz = n * sizeof(*S);
  int i, j;

  long sqrt_n = sqrt(n) + 1;

  printf("%d\n", n);

  S = malloc(sz);
  memset(S, 0, sz);

  for (i = 2; i < sqrt_n; ++i)
    if (S[i] == 0)
      for (j = i*i; j < n; j+=i)
        S[j] = 1;

  count = 0;
  for (i = 2; i < n; ++i)
    if (S[i] == 0)
      count++;

  printf("%d\n", count);

  free(S);
  return 0;
}

Скрипт для запуска (Makefile):

SRC=erato-c-int
N=100000000

all:  build run

build: build-cl build-lcc build-tcc

run: run-cl run-lcc run-tcc

build-cl:
  @cl /nologo /O2 -Fe$(SRC)-cl.exe $(SRC).c

run-cl:
  @echo ---
  -@cl 2>&1 | findstr Compiler
  @ntimer.exe $(SRC)-cl.exe $(N) | findstr ETime

build-lcc:
  @c:\lcc\bin\lcc -O2 -o $(SRC)-lcc.obj $(SRC).c
  @c:\lcc\bin\lcclnk -o $(SRC)-lcc.exe $(SRC)-lcc.obj

run-lcc:
  @echo ---
  @c:\lcc\bin\lcc -v
  @ntimer.exe $(SRC)-lcc.exe $(N) | findstr ETime

build-tcc:
  @c:\tcc\tcc -O2 -o $(SRC)-tcc.exe $(SRC).c

run-tcc:
  @echo ---
  @c:\tcc\tcc -v
  @ntimer.exe $(SRC)-tcc.exe $(N) | findstr ETime

Погнали:

---
Microsoft (R) 32-bit C/C++ Optimizing Compiler Version 16.00.30319.01 for 80x86
ETime(   0:00:04.374 ) UTime(   0:00:04.196 ) KTime(   0:00:00.124 )
---
Logiciels/Informatique lcc-win32 version 3.8. Compilation date: Jan 29 2011 11:51:05
ETime(   0:00:04.415 ) UTime(   0:00:04.102 ) KTime(   0:00:00.202 )
---
tcc version 0.9.25
ETime(   0:00:04.944 ) UTime(   0:00:04.492 ) KTime(   0:00:00.280 )

Вывод не особо захватывающий. Все выступили примерно одинаково.

Посты по теме:

• Решето Эратосфена - кто быстрее: Go, C или C++
• Кто быстрее: vector<bool> или vector<int>

Windows борется с написанием вирусов

Мы тут столкнулись с интересной проблемой - какая-то катастрофически медленная скорость сборки системы под Windows на одной из наших сборочных машин.

Но когда я узнал причину - вот это действительно вызвало у меня минуту молчания.

Причина - это антивирус, а точнее его "активная защита", которая проверяла каждый божий файл (а их там тысячи), генерируемый при сборке. Просто забыли ее выключить при установке системы.

Получается, в принципе, пишу я вирус, компилирую, а тут бабах - и при сборке мне говорят, что результат вашей компиляции был убит, убит еще до того, как успел в первый раз родиться, так как бинарь содержит код, похожий на вирус (я же вирус пишу!).

Ведь антивирус не знает, является ли этот новый файл просто результатом компиляции из исходника, или файл скачивается из интернета.

В общем, отключили антивирус -- сборка ускорилась в разы.

NORCPU hackme challenge или взлом программы для однокомандного процессора

Разного рода "ненормальное" программирование весьма популярно среди любителей поломать голову над разными задачками. Порой программу для очередной "ненормальной" среды программирования уже нереально написать вручную, а надо писать генератор, создающий код.

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

Итак, имеется модель некоторого виртуального процессора, выполняющего только одну логическую операцию - Стрелку Пирса.

На этом процессоре написана программа, на вход которой подается некоторый пароль. Если пароль неверный, то в ответ выдается строка "Wrong password!". Если верный, то выдается определенное волшебное сообщение.

Задача: любым образом выяснить это волшебное сообщение. Как вариант, можно, например, угадать пароль, и программа сама выдаст секрет.

Логика написана таким образом, что разобравшись в алгоритме, можно без труда расшифровать волшебное сообщение.

В прошлом году я описал использованный подход во всех деталях.

Оригинальный подход, на котором основан мой эксперимент, был не совсем "чистым", так как команда сложения был вынесена за логику процессора. В моей версии все до единой команды реализованы на самом процессоре. Для этого потребовалось немного изменить интерпретатор, добавив в него сдвиговый регистр.

Для желающих попробовать взломать мой эксперимент, я сделал страничку, на которой на JavaScript'e реализован выше описанный виртуальный процессор с одной командой и программа для него, проверяющая пароль.

Итак, ссылка на задачу: http://demin.ws/norcpu/norcpu.html

Удачи.

P.S. Для первого взломавшего - небольшой приз! Информация по ссылке.

Плавающая точка уплыла

Решал одну задачу на UVa Online Judge. Долго не мог найти проблему и проверял алгоритм.

Но все было гораздо проще. Как вы думаете, что должна выводить следующая программа?

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  return 0;
}

Я ожидал два числа 115.

Нет, у меня на VS2008 она печатает:

a = 115
b = 114

Вот такие дела.

Update:
Кстати, если попробовать так:

#include <iostream>
#include <cmath>
using namespace std;

int main(int argc, char* argv[]) {
  double f = 1.15;
  int a = f * 100.0 + 0.1E-9;
  int b = f * 100.0;
  cout << "a = " << a << endl;
  cout << "b = " << b << endl;
  double f1 = 0.15;
  int a1 = f1 * 100.0 + 0.1E-9;
  int b1 = f1 * 100.0;
  cout << "a1 = " << a1 << endl;
  cout << "b1 = " << b1 << endl;
  return 0;
}

то результат будет:

a = 115
b = 114
a1 = 15
b1 = 15

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

На ТопКодере есть отличная статья на эту тему (часть 1 и часть 2). Все кратко и по делу.

Веселые перестановки. Решение (сортировка перестановками соседних элементов)

Итак, мое решение вопроса о приведении одной последовательности к другой, когда можно только переставлять два элемента.

Нас просят привести одну последовательность (исходную) к другой (целевой). То есть логично предположить, что одна последовательность в нужном порядке (целевая), а вторая (исходная) - нет. Так надо просто отсортировать исходную последовательность "в целевую".

Так как целевая последовательность по условию не обязательно отсортированная, то при сортировке "к ней" нельзя просто сравнивать элементы исходной последовательности на больше/меньше, так как в этом случае мы получим на выходе сортировку по правилам системы исчисления. В нашем случае надо принять, что целевая последовательность и есть эталонный отсортированный алфавит, и он задает правила сортировки. При сравнении значений из этого алфавита надо понять, в какой позиции алфавита находится значение и использовать его индекс как ключ сортировки (функция less()).

Теперь, а какой алгоритм сортировки использовать, чтобы для перемещения элементов использовать только обмен соседних элементов (функция swap())? Подходит сортировка вставками, когда на каждом шаге неотсортированный элемент последовательно "пропихивается" вниз к отсортированным. Тут как раз можно обойтись только обменом соседних элементов. Сама функция insertion_sort() является универальной и не зависит от компаратора is_less().

#include <stdlib.h>
#include <stdio.h>

void swap(int* a, int i) {
  int t = a[i];
  a[i] = a[i + 1];
  a[i + 1] = t;
}

#define N 8

const int etalon[] = { 1, 5, 7, 4, 2, 9, 8, 6 };
int from[N] = { 8, 1, 4, 2, 5, 6, 9, 7 };

void insertion_sort(int* a, int n, int (*is_less)(int, int)) {
  int i, j;
  for (i = 1; i < n; ++i) 
    for (j = i - 1; j >= 0 && is_less(a[j + 1], a[j]); j--)
      swap(a, j);
}

void print_array(const char* title, const int* a, int n) {
  int i;
  printf("%9s: ", title);
  for (i = 0; i < n; ++i)
    printf("%d ", a[i]);
  printf("\n");
}

int less(int a, int b) {
  int ia = -1, ib = -1;
  int i;
  for (i = 0; i < N; ++i) {
    if (etalon[i] == a) ia = i;
    if (etalon[i] == b) ib = i;
    if (ia >= 0 && ib >= 0) break;
  }
  return ia < ib;
}

int main() {
  int i, j;

  print_array("Original", from, N);
  insertion_sort(from, N, less);
  print_array("Converted", from, N);
  print_array("Etalon", etalon, N);

  return 0;
}

Запускаем:

 Original: 8 1 4 2 5 6 9 7 
Converted: 1 5 7 4 2 9 8 6 
   Etalon: 1 5 7 4 2 9 8 6 

Вроде работает.

Теперь что со сложностью. Принято считать, что сортировка вставками - это O(N^2) для худшего случая. Так как для сравнения элементов нам приходится искать линейно по эталонной последовательности на каждом шаге, то это еще O(N). В этоге: O(N^3).

Как вариант ускорения, можно изначально сделать отсортированную по значениям копию эталонной последовательности, и хранить не только значение, но его индекс. В этом случае поиск элемента будет уже занимать не O(N), а O(log(N)), и общая сложность будет O(log(N)*N^2).

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

Указание на эти два факта лично я счел бы на однозначно достаточный ответ.

Модель процессора с одной командой

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

В середине 90-x, в эхо-конференции Фидо RU.HACKER, небезысвестный Solar Designer (он же Alexander Peslyak, автор таких вещей как John The Ripper и Openwall Linux), опубликовал интересную программу собственного сочинения, и предлагал попробовать ее взломать, угадав пароль, который она запрашивает и проверяет.

В отличие от большинства подобных hackme, в программе не было трюков, затрудняющих работу отладчика. Единственная трудность - это логика самой программы, так весь ее исполняемый код - это менее 100 байт интерпретатора виртуальной машины, которая умеет делать только одну операцию - NOR (или Стрелку Пирса).

У этой виртуальной машины память линейна и стоит из 16-х битных слов. Данные и исполняемый код могут перемешиваться. Каждая инструкция состоит из трех слов - адресов операндов. Исполнение инструкции - это в чтении из памяти двух слов, адреса которых лежат в первых двух операндах, проведения между ними операции NOR и записи результата по адресу, заданному в третьем операнде. После выполнения инструкции указатель команд увеличивается на 3 (чтобы указывать на следующую инструкцию), и все повторяется сначала.

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

cld
emCPU:
mov  si,emIP
lodsw
xchg ax,di
mov  di,[di]
lodsw
xchg ax,bx
or   di,[bx]
lodsw
xchg ax,di
not  ax
mov  emIP,si
stosw
jmp  short emCPU

Но ни что не мешает перенести его в мир, например, Питона (тут вместо NOR используется NAND):

def nand(a, b):
  return ~(a & b) & 0xFFFF

def norcpu():
  while 1:
    i = mem[IP];
    a = mem[i + 0]
    b = mem[i + 1]
    r = mem[i + 2]
    mem[IP] = i + 3
    f = nand(mem[a], mem[b])
    mem[r] = f

Почему именно NOR? Из теории булевой алгебры известно, что любую из 14-ти логических функций (например, NOT, AND, OR, XOR и т.д., всего их 16) двух одно битовых аргументов можно выразить через функции NOR и NAND. Например:

NOT(a) = NAND(a, a)
AND(a, b) = NAND(NAND(a, b), NAND(b, a))
OR(a, b) = NAND(NAND(a, a), NAND(b, b))
XOR(a, b) = OR(AND(a, NOT(b)), AND(NOT(a), b)))

Пересылка данных MOVE(src, dst) может быть сделана через OR:

mem[dst] = OR(mem[src], mem[src])

Условный переход также реализуется через булеву логику. Если cond равно 0xFFFF (истина), то осуществляется переход на адрес addr, а если cond равно 0x0000, то выполнение продолжается линейно:

mem[IP] = OR(AND(addr, cond), AND(mem[IP], cond))

или в нотации интерпретатора:

AND addr, cond, @t1
AND IP, cond, @t2
OR @t1, @t2, IP

где @t1 и @t2 - некоторые вспомогательные переменные. Команды AND и OR также раскрываются в последовательность элементарных NOR, как было показано ранее.

Что получается: булевы операции есть, пересылка данных есть, команды условного и безусловного переходов есть - для полноты не хватает операций сложения/вычитания и сдвигов. После этого уже можно программно реализовать стек и получить полноценную вычислительную среду.

Вот тут в оригинальной программе Александра был трюк, с помощью которого можно было вызывать native код x86. Так как код самого интерпретатора на ассемблере x86 также находился в адресном пространстве виртуальной машины, то в нужный момент в начало интерпретатора командой MOVE подставлялась двухбайтовая команда перехода x86 (то есть интерпретатор сам себя модифицировал), по адресу перехода которой находился нужный native код x86. После его выполнения восстанавливались оригинальные первые два байты интерпретатора, интерпретация продолжалась в обычном режиме.

Именно так была реализована команда сложения и несколько утилитарных вызовов прерываний DOS для печати на экран и ввода с клавиатуры.

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

Кроме того, если писать интерпретатор на произвольном языке, например Питоне, то для выполнения стороннего кода, который не получается реализовать в рамкам интерпретатора, надо как-то перехватывать управление, и идея машины только на одной операции NOR перестает быть "чистой".

Лирическое отступление. Я всегда интересовался reverse engineering'ом (даже сейчас не прочь покопаться IDA'ой в каком-нибудь экзешнике), и в частности различными идеями защиты от отладки. А данная идея интерпретатора одной команды тут подходит как нельзя лучше. Так как все реализовано через одну элементарную функцию, то при анализе и дизассемблировании сложно понять, где границы высокоуровневых команд. Как одну из идей, я переделал свой простейший Форт-интерпретатор с прямым шитым кодом (который сам по себе затруднен для анализа) под использование NOR интерпретатора для реализации всех низкоуровневых Форт-примитивов.

Недавно я вернулся к теме NOR-интерпретатора. Интересно было написать это на Питоне. Также пришла мысль, как можно модифицировать интерпретатор, чтобы на нем можно было бы реализоваться и полноценное сложение.

Я ввел одну дополнительную команду в него — циклический сдвиг результата каждой операции и сохранение значения в специальной ячейке-регистре:

def norcpu():
  while 1:
    i = mem[IP];
    a = mem[i + 0]
    b = mem[i + 1]
    r = mem[i + 2]
    mem[IP] = i + 3
    f = nand(mem[a], mem[b])
    mem[r] = f
    mem[S] = ((f >> 31) & 1) | ((f & 0x7FFF) << 1)

То есть теперь есть две особые ячейки: IP (instruction pointer) и S (значение последней операции, циклически сдвинутое влево).

Попробуем реализовать полное суммирование 16-х слов с переносом. Я буду писать на некотором элементарном макро-ассемблере.

Итак, полный однобитный сумматор в нотации булевой алгебры:

sum = (a ^ b) ^ carry
carry = (a & b) | (carry & (a ^ b))

Теперь на языке NOR(NAND)-процессора:

; Вход:
;  mask  - битовая маска рабочего бита (0x0001, 0x0002, 0x0004, 0x0008 и т.д.)
;  carry - перенос от предыдущего бита (бит определяется маской mask)
;  a, b  - адреса аргументов
;  r     - адрес результата
; Выход:
;  r     - результат
;  carry - перенос для следующего разряда (по отношению к mask уже сдвинут на 1 бит влево)
;  mask  - маска, сдвинутая слево на 1 бит
;
; Переменные с префиксом '@' - локальные для этого макроса.
;
!macro FADD mask, carry, a, b, r
  AND a, mask, @bit_a        ; Уберем в "a" все биты, кроме нужного.
  AND b, mask, @bit_b        ; Уберем в "b" все биты, кроме нужного.
  AND carry, mask, carry     ; Уберем в переносе все биты, кроме нужного.
  XOR a, b, @t1              ; Формула: sum = (a ^ b) ^ carry.
  XOR @t1, carry, @bit_r     ; 
  AND @bit_r, mask, @bit_r   ; Уберем из @bit_r все биты, кроме текущего 
                             ; по маске.
  OR @bit_r, r, r            ; Наложим текущий сложенный бит на результат: 
                             ; r |= sum
  AND a, b, @t2              ; Формула: carry = (a & b) | (carry & (a ^ b))
  AND carry, @t1, @t1        ;
  OR @t2, @t1, carry         ; Перенос получил новое значение. Регистр S
                             ; равен ему же, но сдвинутому влево на 1 бит. 
  MOVE S, carry              ; Теперь перенос равен себе же, но со сдвигом
                             ; влево на 1 (для суммирования в следующем бите).
  MOVE mask, mask, mask      ; Пустое присваивание mask самой себе, чтобы
                             ; получить сдвинутое значение в S.
  MOVE S, mask               ; Маска сдвинута влево на 1 бит для суммирования
                             ; следующего бита: mask = S = mask << 1

И теперь сам макрос полного суммирования:

; Вход:
;  a, b  - аргументы
;  carry - перенос (0 или 1 в младшем разряде)
; Выход:
;  r     - результат
;  carry - перенос (0 или 1 в младшем разряде)
;
; Переменные с префиксом '@' - локальные для этого макроса.
; const_1 - специальная ячейка, в которой содержится 0x0001.
;
!macro ADC a, b, carry, r
  XOR r, r, r                     ; Запишем 0 в r.
  MOVE const_1, @mask             ; Начальное значение маски: 0x0001
  *16 FADD @mask, carry, a, b, r  ; Повторяем FADD 16 раз (просто линейно в
                                  ; памяти, никаких циклов).
  AND carry, const_1, carry       ; Почистим перенос от мусора в старших
                                  ; разрядах.

Что происходить в ADC? При каждом повторении FADD происходит суммирование текущего бита, маска которого задана в mask. Просуммированный бит добавляется (через OR) в результат. Кроме этого mask автоматически сдвигается влево на 1 бит, чтобы указывать на следующей бит (0x0001 -> 0x0002 -> 0x0004 и т.д.). Также в каждом вызове FADD перенос после суммирования тоже сдвигается влево на 1 бит, чтобы быть готовым для суммирования на следующей итерации. После суммирования последнего 16-го бита перенос уйдет снова в самый младший разряд (так как интерпретатор делает циклический сдвиг), и это значение и будет результирующим переносом после всего суммирования.

Все, сложение у нас есть. Далее дело техники. Реализация стека чисто программная. Команды вызовы подпрограммы и возврата на место вызова реализуются уже через механизм стека и команд перехода.

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

Машина крайне проста, но из-за этого программный код, состоящий из примитивных NOR'ов (или NAND'ов) может быть большим.

Для чего? Первое и главное: академический интерес. Прикольно же получить полноценную вычислительную среду на базе единственной операции NOR или NAND. Второе: изначально все это задумывалось как вариант защиты, например, от копирования. На данной виртуальной машине можно реализовать хитрую крипто-функцию и ей проверять валидность ключа. Таким образом к крипто-защите еще и добавится трудный анализа кода.

Но на дворе время opensource, то что повторюсь - академический интерес!

Посты по теме:

• Обмен двух переменных через XOR

Обмен двух переменных через XOR

Чтобы поменять местами значения двух целочисленных переменных кроме как через использование дополнительной переменной, можно сделать так:

a += b;
b = a - b;
a -= b;

Интересно разве что с академической точки зрения. Но есть способ интереснее:

a ^= b ^= a ^= b;

который также меняет местами значения этих переменных.

Update: В комментариях подсказали грамотную ссылку по трюкам с битовой арифметикой.

Коварный printf()

Вчера подорвался на ерунде как ребенок.

Сижу, отлаживаю новый онлайновый ассемблер в своем эмуляторе Радио-86РК. Под отладкой понимается ёрзанье с применением html'я.

Для сборки финального html-файла из кучи мелких у меня написана примитивная программа. Вот ее фрагмент:

...
  while (!feof(f)) {
    char line[1024];
    *line = 0;
    fgets(line, sizeof(line), f);
    printf(line);
  }
...

Подразумевается, что данный код прострочно копирует данные из файла f на стандарный вывод.

Даже если отставить в сторону использование буфера с константной длиной и прочих "штучек" языка С, этот код имеет одну проблему, которая стоила мне сомнений в наличии сознания. До каких-то пор все работало отлично, но как только я начал использовать процентные значения для широт и высот в html, начались странности. Получалось, что вместо, например:

<table width="100%">

на выходе было:

<table width="100">

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

Вместо:

printf(line);

надо писать:

printf("%s", line);

А иначе все процентные символы будут расцены как указатели форматов, ибо первый параметр printf() - это не просто строка, а формат, и в случае их неэкранирования будут уделены, что и происходило в моем случае.

Вывод (который следует после начального "сам дурак"): Лучше писать на С++ и использовать потоки для форматного вывода.

Лирическое отступление. Кстати, онлайновый ассемблер очень огранично вписался в эмулятор. Спасибо Вячеславу Славинскому за оригинальный код этого ассемблера. Особенно меня радует возможность автоматической фоновой компиляции. Теперь можно, прямо не отходя от эмулятора, переключиться в ассемблер, написать что-нибудь на диалекте Intel 8080 (КР580), скомпилировать и загнать прямо в эмулятор.

const T* или T const*

Не секрет, что выражение "const T*" при объявления указателя полностью эквивалентно записи "T const*", ибо тут важно только, что const стоит до знака *, а порядок его употребления с именем типа Т роли не играет:

const T* p;

и

T const* p;

объявляют указатель на константный объект, а не константный указатель, то есть значение самого указателя можно менять:

T const* p;
...
p = NULL;

Но менять сам объект нельзя:

T const* p;
...
p->some_member = 0;   // ОШИБКА: error C2166: l-value specifies const object

Но все это была вводная, и сейчас не об этом.

Меня больше интересуют читабельность исходников. Я могу ошибаться, но как мне кажется, что с общечеловеческой точки зрения употребление const в начале выражения (например, "const T* p;") подразумевает константность всего выражения, и, собственно, не важно, что там на самом деле указатель, и по правилам С++ данный const значит только константность объекта, а не указателя.

Поэтому запись "T const* p;" может читаться несколько иначе, а именно: "тип T, который константный, и на него объявляется указатель. Читабельность немного лучше.

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

Двойная точка с запятой в разделе объявления переменных

Казалось бы, невинный пример (vs_double_semicolumn.c):

void main() {
  int a;;
  int b;
}

Компилируем (в режиме языка С, то есть без /TP):

cl vs_double_semicolumn.c

Результат:

vs_double_semicolumn.c
vs_double_semicolumn.c(3) : error C2143: syntax error : missing ';' before 'type'

Результат в Codegear/Borland примерно такой же (хотя описание ошибки более ясное):

CodeGear C++ 5.93 for Win32 Copyright (c) 1993, 2007 CodeGear
vs_double_semicolumn.c:
Error E2140 vs_double_semicolumn.c 3: Declaration is not allowed here in function main
*** 1 errors in Compile ***

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

Получается, что второй символ ; тут трактуется как пустой оператор, а не пустая декларация переменной. Компилятор решает, что объявления переменных закончены, и начался блок операторов, поэтому резонно ругается на попытку объявить переменную b там, где уже должны быть операторы.

Проверил на gcc, на родных компиляторах AIX, Solaris и HP-UX. Эти все съели пример без проблем.

Посты по теме:

• Ошибка в компиляторе Godegear (Borland) C++ при приведении типов указателей

Ошибка в компиляторе Godegear (Borland) C++ при приведении типов указателей

Тривиальный пример (bcc32_5.93_cast_bug.cpp):

class A {};
class C {};
A* a;
A* b = static_cast<C*>(a);

Компилируем в bcc32.exe (версия 5.93) из Codegear RAD Studion 2007:

bcc32 -c bcc32_5.93_cast_bug.cpp

Падает c internal compiler error:

CodeGear C++ 5.93 for Win32 Copyright (c) 1993, 2007 CodeGear
bcc32_5.93_cast_bug.cpp:
Fatal F1004 bcc32_5.93_cast_bug.cpp 4: Internal compiler error at 0x44b34e with base 0x400000
Fatal F1004 bcc32_5.93_cast_bug.cpp 4: Internal compiler error

Люблю собирать падения компиляторов на стадии компиляции. А у вас есть что-нибудь подобное в загашнике?

Виртуальные функции в конструкторе и деструкторе

Рассмотрим простой пример (virtual_funct_const.cpp):

#include <iostream>

class A {
 public:
  A() {
    construct();
  }

  ~A() {
    destruct();
  }

  virtual void construct() {
    std::cout << "A::construct()" << std::endl;
  }

  virtual void destruct() {
    std::cout << "A::destruct()" << std::endl;
  }
};

class B: public A {
 public:
  B() {
    construct();
  }

  ~B() {
    destruct();
  }

  virtual void construct() {
    std::cout << "B::construct()" << std::endl;
  }

  virtual void destruct() {
    std::cout << "B::destruct()" << std::endl;
  }
};

int main() {
  B b;
  return 0;
}

Что напечатает эта программа?

А вот что:

A::construct()
B::construct()
B::destruct()
A::destruct()

Получается, что конструкторы и деструкторы классов A и B при вызове объявленных виртуальными функций construct() и destruct() реально вызывали функции только своего класса.

В этом нет никакого секрета, а просто есть правило: виртуальная функция не является виртуальной, если вызывается из конструктора или деструктора.

Правило надо заучивать, что неудобно. Проще понять принцип. А принцип тут в краеугольном камне реализации наследования в C++: при создании объекта конструкторы в иерархии вызываются от базового класса к самому последнему унаследованному. Для деструкторов все наоборот.

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

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

Итак, виртуальная функция не является виртуальной, если вызывается из конструктора или деструктора.