Алгоритм CRC

Я бы хотел расскажать об интересном алгоритме CRC ( сyclic redundancy check ). С помощью этого алгоритма можно не только использовать для проверки целострости данных, но и для других полезных целей. Приведу простой вариант алгорима:

uint64_t crc_calc_slow( uint64_t poly, uint64_t crc, const void * buffer, size_t size )
{
    while( size-- ) {
        crc ^= * ( uint8_t * ) buffer++;
        int bit = 8;
        while( bit-- ) crc = crc & 1 ? ( crc >> 1 ) ^ poly : crc >> 1;
    }
    return crc;
}

где:
    poly - полином
    crc - начальное либо предыдущее состояние crc
    buffer - указатель на блок в памяти
    size - размер блока

это простой и медленно работающий вариант алгоритма т.к. для каждого байта ему нужно сделать 8 итераций, потому его на практике используют табличный вариант который обрабатывает 1 байт за итерацию, по моим тестам работаетающий где то в 10 раз быстрее. Табличный вариант можете найти в интернете или в моем пакете http://sourceforge.net/projects/csnippets

CRC файла можно вычислить сразу для всего файла или последовательно порциями указав для функции предыдыщий вычисленный CRC;

вот пример:

вычислим CRC для всего сообщения:
crc_calc_slow( POLY, 0, "MESSAGE", strlen( "MESSAGE" ) ) ==
0x1494111b;

а вот для двух частей "МЕSS" и "AGE"
crc_calc_slow( POLY, 0, "MESS", strlen( "MESS" ) ) == 0x7cdbc112
crc_calc_slow( POLY, 0x7cdbc112, "AGE", strlen( "AGE" ) ) ==
0x1494111b

т.е. сначала мы вычиляем CRC части сообщения "MESS" с начальным значением 0 и получим 0x7cdbc112, а затем вычислим CRC для другой части сообщения "AGE" с начальным значение 0x7cdbc112 и получим значение 0x1494111b.

Сборка программ из исходников

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

1. распаковать архив
2. сконфигурировать
3. скомпилировать
4. собрать пакет

Понятно что если пакетов большое количество то собирать руками займет много времени. Для себя я сделал bash скрипт который делает это автоматически:

-----------------------------------------------------------------------
#!/bin/sh

if [ $# -ne 1 ]; then
    echo "build package from source"
    echo "usage: `basename $0` filename.{tar.gz|tar.bz2|tar.xz}"
    exit 1
fi

TMP=/tmp/BS-$$ #TMP=/tmp/BS-`uuidgen | head -c 8`
PKG=`realpath $1 || exit 1`
PREFIX=/usr

case "$( uname -m )" in
  x86_64) LIBDIR=$PREFIX/lib64 ;;
    i?86) LIBDIR=$PREFIX/lib ;; # $PREFIX/lib32
       *) LIBDIR=$PREFIX/lib ;;
esac

mkdir $TMP
cd    $TMP

tar -xvf "$PKG" || exit 1
PKGNAME=`ls $TMP`
cd $PKGNAME

[ -f CMakeLists.txt ] && (cmake . -DCMAKE_INSTALL_PREFIX:PATH=$PREFIX -DLIB_SUFFIX:PATH=$LIBDIR || exit 1) #-DCMAKE_C_FLAGS:STRING="" -DCMAKE_CXX_FLAGS:STRING="" -DMAN_INSTALL_DIR=/usr/man -DCMAKE_BUILD_TYPE=Release

[ -f configure ] && (./configure --prefix=$PREFIX --libdir=$LIBDIR || exit 1)

NUMJOBS=${NUMJOBS:--j`nproc`} #NUMJOBS=${NUMJOBS:--j`cat /proc/cpuinfo | grep processor | wc -l`}
make $NUMJOBS || exit 1 # unfortunatly make don't return fail but may be

mkdir $TMP/root
make install DESTDIR=$TMP/root # make install-strip DESTDIR=$TMP/root

cd $TMP/root

# strip binaries:
find . | xargs file | grep "executable"    | grep ELF | cut -f 1 -d : | xargs strip --strip-unneeded 2> /dev/null
find . | xargs file | grep "shared object" | grep ELF | cut -f 1 -d : | xargs strip --strip-unneeded 2> /dev/null

cd $TMP/root
tar cf - . | gzip > /tmp/$PKGNAME.tgz

echo ----------------------------------------------------------
echo Package /tmp/$PKGNAME.tgz built

rm -rf $TMP