Index: MicroBenchmarks/harris/CMakeLists.txt =================================================================== --- MicroBenchmarks/harris/CMakeLists.txt +++ MicroBenchmarks/harris/CMakeLists.txt @@ -0,0 +1,4 @@ +list(APPEND CPPFLAGS -std=c++11 ) +llvm_test_run() +llvm_test_executable(harris harris_kernel.cpp init.cpp main.cpp sha1.cpp) +target_link_libraries(harris benchmark) Index: MicroBenchmarks/harris/harris.h =================================================================== --- MicroBenchmarks/harris/harris.h +++ MicroBenchmarks/harris/harris.h @@ -0,0 +1,36 @@ +#include +#include +#include +#include +#include +#include + +// ============================================================================ +// ============================================================================ + +// Image Size +#define HEIGHT 100 +#define WIDTH 100 +// (Any box size will work) +// This parameter is used in input // used only in init_checkboard_image +#define BOX_SIZE 10 + +// ============================================================================ +// ============================================================================ + +// Some Parameters +#define THRESHOLD 0.1 /*For harris kernel*/ + +// ============================================================================ +// ============================================================================ + +void init_checkboard_image(int height, int width); // Initialize a checkboard image +void write_to_file(int height, int width, float *array); +int check_output(); +void harris_kernel(int R, int C, float threshold, float * imag); + +// ============================================================================ + +extern float *__restrict__ image; + +// ============================================================================ Index: MicroBenchmarks/harris/harris_kernel.cpp =================================================================== --- MicroBenchmarks/harris/harris_kernel.cpp +++ MicroBenchmarks/harris/harris_kernel.cpp @@ -0,0 +1,148 @@ +#include "harris.h" + +// harris kernel from polymage_naive.cpp +void harris_kernel(int R, int C, float threshold, float *__restrict__ imag) { + float *img; + img = (float *)imag; + float *Ix; + Ix = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *Iy; + Iy = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *Ixx; + Ixx = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *Ixy; + Ixy = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *Iyy; + Iyy = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *Sxx; + Sxx = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *Sxy; + Sxy = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *Syy; + Syy = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *det; + det = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + float *trace; + trace = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + + for (int _i0 = 1; (_i0 <= R); _i0 = (_i0 + 1)) { + for (int _i1 = 1; (_i1 <= C); _i1 = (_i1 + 1)) { + Iy[((_i0 * (2 + C)) + _i1)] = + ((((((img[(((-1 + _i0) * (C + 2)) + (-1 + _i1))] * + -0.0833333333333f) + + (img[(((-1 + _i0) * (C + 2)) + (1 + _i1))] * 0.0833333333333f)) + + (img[((_i0 * (C + 2)) + (-1 + _i1))] * -0.166666666667f)) + + (img[((_i0 * (C + 2)) + (1 + _i1))] * 0.166666666667f)) + + (img[(((1 + _i0) * (C + 2)) + (-1 + _i1))] * -0.0833333333333f)) + + (img[(((1 + _i0) * (C + 2)) + (1 + _i1))] * 0.0833333333333f)); + } + } + for (int _i0 = 1; (_i0 <= R); _i0 = (_i0 + 1)) { + for (int _i1 = 1; (_i1 <= C); _i1 = (_i1 + 1)) { + Ix[((_i0 * (2 + C)) + _i1)] = + ((((((img[(((-1 + _i0) * (C + 2)) + (-1 + _i1))] * + -0.0833333333333f) + + (img[(((1 + _i0) * (C + 2)) + (-1 + _i1))] * 0.0833333333333f)) + + (img[(((-1 + _i0) * (C + 2)) + _i1)] * -0.166666666667f)) + + (img[(((1 + _i0) * (C + 2)) + _i1)] * 0.166666666667f)) + + (img[(((-1 + _i0) * (C + 2)) + (1 + _i1))] * -0.0833333333333f)) + + (img[(((1 + _i0) * (C + 2)) + (1 + _i1))] * 0.0833333333333f)); + } + } + + for (int _i0 = 1; (_i0 <= R); _i0 = (_i0 + 1)) { + for (int _i1 = 1; (_i1 <= C); _i1 = (_i1 + 1)) { + Iyy[((_i0 * (2 + C)) + _i1)] = + (Iy[((_i0 * (2 + C)) + _i1)] * Iy[((_i0 * (2 + C)) + _i1)]); + } + } + for (int _i0 = 1; (_i0 <= R); _i0 = (_i0 + 1)) { + for (int _i1 = 1; (_i1 <= C); _i1 = (_i1 + 1)) { + Ixy[((_i0 * (2 + C)) + _i1)] = + (Ix[((_i0 * (2 + C)) + _i1)] * Iy[((_i0 * (2 + C)) + _i1)]); + } + } + + for (int _i0 = 1; (_i0 <= R); _i0 = (_i0 + 1)) { + for (int _i1 = 1; (_i1 <= C); _i1 = (_i1 + 1)) { + Ixx[((_i0 * (2 + C)) + _i1)] = + (Ix[((_i0 * (2 + C)) + _i1)] * Ix[((_i0 * (2 + C)) + _i1)]); + } + } + for (int _i0 = 2; (_i0 < R); _i0 = (_i0 + 1)) { + for (int _i1 = 2; (_i1 < C); _i1 = (_i1 + 1)) { + Syy[((_i0 * (2 + C)) + _i1)] = + ((((((((Iyy[(((-1 + _i0) * (2 + C)) + (-1 + _i1))] + + Iyy[(((-1 + _i0) * (2 + C)) + _i1)]) + + Iyy[(((-1 + _i0) * (2 + C)) + (1 + _i1))]) + + Iyy[((_i0 * (2 + C)) + (-1 + _i1))]) + + Iyy[((_i0 * (2 + C)) + _i1)]) + + Iyy[((_i0 * (2 + C)) + (1 + _i1))]) + + Iyy[(((1 + _i0) * (2 + C)) + (-1 + _i1))]) + + Iyy[(((1 + _i0) * (2 + C)) + _i1)]) + + Iyy[(((1 + _i0) * (2 + C)) + (1 + _i1))]); + } + } + for (int _i0 = 2; (_i0 < R); _i0 = (_i0 + 1)) { + for (int _i1 = 2; (_i1 < C); _i1 = (_i1 + 1)) { + Sxy[((_i0 * (2 + C)) + _i1)] = + ((((((((Ixy[(((-1 + _i0) * (2 + C)) + (-1 + _i1))] + + Ixy[(((-1 + _i0) * (2 + C)) + _i1)]) + + Ixy[(((-1 + _i0) * (2 + C)) + (1 + _i1))]) + + Ixy[((_i0 * (2 + C)) + (-1 + _i1))]) + + Ixy[((_i0 * (2 + C)) + _i1)]) + + Ixy[((_i0 * (2 + C)) + (1 + _i1))]) + + Ixy[(((1 + _i0) * (2 + C)) + (-1 + _i1))]) + + Ixy[(((1 + _i0) * (2 + C)) + _i1)]) + + Ixy[(((1 + _i0) * (2 + C)) + (1 + _i1))]); + } + } + for (int _i0 = 2; (_i0 < R); _i0 = (_i0 + 1)) { + for (int _i1 = 2; (_i1 < C); _i1 = (_i1 + 1)) { + Sxx[((_i0 * (2 + C)) + _i1)] = + ((((((((Ixx[(((-1 + _i0) * (2 + C)) + (-1 + _i1))] + + Ixx[(((-1 + _i0) * (2 + C)) + _i1)]) + + Ixx[(((-1 + _i0) * (2 + C)) + (1 + _i1))]) + + Ixx[((_i0 * (2 + C)) + (-1 + _i1))]) + + Ixx[((_i0 * (2 + C)) + _i1)]) + + Ixx[((_i0 * (2 + C)) + (1 + _i1))]) + + Ixx[(((1 + _i0) * (2 + C)) + (-1 + _i1))]) + + Ixx[(((1 + _i0) * (2 + C)) + _i1)]) + + Ixx[(((1 + _i0) * (2 + C)) + (1 + _i1))]); + } + } + for (int _i0 = 2; (_i0 < R); _i0 = (_i0 + 1)) { + for (int _i1 = 2; (_i1 < C); _i1 = (_i1 + 1)) { + trace[((_i0 * (2 + C)) + _i1)] = + (Sxx[((_i0 * (2 + C)) + _i1)] + Syy[((_i0 * (2 + C)) + _i1)]); + } + } + for (int _i0 = 2; (_i0 < R); _i0 = (_i0 + 1)) { + for (int _i1 = 2; (_i1 < C); _i1 = (_i1 + 1)) { + det[((_i0 * (2 + C)) + _i1)] = + ((Sxx[((_i0 * (2 + C)) + _i1)] * Syy[((_i0 * (2 + C)) + _i1)]) - + (Sxy[((_i0 * (2 + C)) + _i1)] * Sxy[((_i0 * (2 + C)) + _i1)])); + } + } + for (int _i0 = 2; (_i0 < R); _i0 = (_i0 + 1)) { + for (int _i1 = 2; (_i1 < C); _i1 = (_i1 + 1)) { + int value = (det[((_i0 * (2 + C)) + _i1)] - + ((0.04f * trace[((_i0 * (2 + C)) + _i1)]) * + trace[((_i0 * (2 + C)) + _i1)])); + if (value > threshold) + img[(_i0 * (2 + C)) + _i1] = 3; + } + } + + free(Ix); + free(Iy); + free(Ixx); + free(Ixy); + free(Iyy); + free(Sxx); + free(Sxy); + free(Syy); + free(det); + free(trace); + return; +} Index: MicroBenchmarks/harris/init.cpp =================================================================== --- MicroBenchmarks/harris/init.cpp +++ MicroBenchmarks/harris/init.cpp @@ -0,0 +1,56 @@ +#include "harris.h" +#include "sha1.hpp" +// This function initializes the input image to checkbox image +// Can be replaced with any other image initialization +void init_checkboard_image(int height, int width) { + image = (float *)malloc((HEIGHT + 2) * (WIDTH + 2) * sizeof(float)); + // 2 different x and y, as we want alternate in both direction + int last_pixel_x = 0; + int last_pixel_y = 0; + + // Initialize a random image + for (int i = 0; i < height; i++) { + if (i % BOX_SIZE == 0) { + last_pixel_y = (last_pixel_y + 1) % 2; + } + last_pixel_x = last_pixel_y; + for (int j = 0; j < width; j++) { + if (j % BOX_SIZE == 0) { + last_pixel_x = (last_pixel_x + 1) % 2; + } + if (last_pixel_x == 0) + image[i * width + j] = 255; + else + image[i * width + j] = 0; + } + } +} + + +// Writes image matrix to a file (asuming values are only 0, 255 and 3. +// If different values are also there then remove % 8 +void write_to_file(int height, int width, float *array) { + std::ofstream myfile; + myfile.open("output.txt"); + + for (int i = 0; i < height - 2; i++) { + for (int j = 0; j < width - 2; j++) { + myfile << int(array[i * (width) + j]) % 8; + } + myfile << "\n"; + } +} + + +int check_output() { + std::string filename = "output.txt"; + SHA1 checksum; + std::string checksum_val = checksum.from_file(filename); + std::cout << "Computed SHA1SUM of output.txt is \"" << checksum_val << "\"" + << std::endl; + + if (checksum_val == "9ad2cea9248750ad10d559bae830640ee1ca16d9") { + return 1; + } + return 0; +} Index: MicroBenchmarks/harris/main.cpp =================================================================== --- MicroBenchmarks/harris/main.cpp +++ MicroBenchmarks/harris/main.cpp @@ -0,0 +1,121 @@ +/* For polymage-benchmarks-harris kernel + Copyright (c) 2015 Indian Institute of Science + All rights reserved. + + Written and provided by: + Ravi Teja Mullapudi, Vinay Vasista, Uday Bondhugula + Dept of Computer Science and Automation + Indian Institute of Science + Bangalore 560012 + India + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + 1. Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + + 2. Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in the + documentation and/or other materials provided with the distribution. + + 3. Neither the name of the Indian Institute of Science nor the + names of its contributors may be used to endorse or promote products + derived from this software without specific prior written permission. + + THIS MATERIAL IS PROVIDED BY Ravi Teja Mullapudi, Vinay Vasista, and Uday + Bondhugula, Indian Institute of Science ''AS IS'' AND ANY EXPRESS OR IMPLIED + WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO + EVENT SHALL Ravi Teja Mullapudi, Vinay Vasista, CSA Indian Institute of + Science BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS + INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN + CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + POSSIBILITY OF SUCH DAMAGE. +*/ + +// ============================================================================ +/* + * Pankaj Kukreja + * Indian Institute of Technology Hyderabad + * + * Acknowledgements + // ============================================================================ + * SHA1SUM computation source code from: + * https://github.com/vog/sha1 + * 100% Public Domain + // ============================================================================ + * HARRIS KERNEL (modified) + * https://github.com/bondhugula/polymage-benchmarks/ + * File: polymage-benchmarks/apps/harris/harris_polymage_naive.cpp +*/ +// ============================================================================ + + + +#include "harris.h" + +float *__restrict__ image = NULL; + +#define BENCHMARK_LIB /* Comment this to not use google benchmark library*/ +#ifdef BENCHMARK_LIB +#include "benchmark/benchmark.h" +#endif + + +/* +This function is called in bechmark macro +-> Since the kernel modifes the original image array, I had to copy values to a +temporary array and then pass that array and then write the output to file. If +there is any better way to do this let me know. + +-> If I do not copy the values and directly pass image array, then some thread +may read the modified value of image array instead of original value. +*/ + +#ifdef BENCHMARK_LIB + void BENCHMARK_HARRIS(benchmark::State &state) { + int R = HEIGHT; + int C = WIDTH; + float *img; + img = (float *)(malloc( + (sizeof(float) * ((2 + R) * (2 + C))))); // for first free + for (auto _ : state) { + state.PauseTiming(); + free(img); + img = (float *)(malloc((sizeof(float) * ((2 + R) * (2 + C))))); + std::memcpy(img, image, (2 + R) * (2 + C) * sizeof(float)); + state.ResumeTiming(); + harris_kernel(HEIGHT, WIDTH, THRESHOLD, img); + } + write_to_file(HEIGHT + 2, WIDTH + 2, img); + free(img); +} +BENCHMARK(BENCHMARK_HARRIS); +#endif + + +int main(int argc, char *argv[]) { + init_checkboard_image((HEIGHT + 2), (WIDTH + 2)); +#ifdef BENCHMARK_LIB + ::benchmark::Initialize(&argc, argv); + if (::benchmark::ReportUnrecognizedArguments(argc, argv)) + return 1; + ::benchmark::RunSpecifiedBenchmarks(); +#else + harris_kernel(image); + write_to_file(HEIGHT + 2, WIDTH + 2, image); +#endif + free(image); + int passed = check_output(); + if (!passed) { + std::cout << "Verification Failed\n"; + exit(EXIT_FAILURE); + } else { + std::cout << "Verification Passed\n"; + exit(EXIT_SUCCESS); + } +} Index: MicroBenchmarks/harris/output.txt =================================================================== --- MicroBenchmarks/harris/output.txt +++ MicroBenchmarks/harris/output.txt @@ -0,0 +1,100 @@ +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777777000000000077777777770000000000777777777700000000007777777777000000000077777777770000000000 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +7777777733330000003333777777333300000033337777773333000000333377777733330000003333777777333300000033 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000000777777777700000000007777777777000000000077777777770000000000777777777700000000007777777777 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 +0000000033337777773333000000333377777733330000003333777777333300000033337777773333000000333377777733 Index: MicroBenchmarks/harris/sha1.hpp =================================================================== --- MicroBenchmarks/harris/sha1.hpp +++ MicroBenchmarks/harris/sha1.hpp @@ -0,0 +1,45 @@ +/* + sha1.hpp - header of + + ============ + SHA-1 in C++ + ============ + + 100% Public Domain. + + Original C Code + -- Steve Reid + Small changes to fit into bglibs + -- Bruce Guenter + Translation to simpler C++ Code + -- Volker Diels-Grabsch + Safety fixes + -- Eugene Hopkinson +*/ + +#ifndef SHA1_HPP +#define SHA1_HPP + + +#include +#include +#include + + +class SHA1 +{ +public: + SHA1(); + void update(const std::string &s); + void update(std::istream &is); + std::string final(); + static std::string from_file(const std::string &filename); + +private: + uint32_t digest[5]; + std::string buffer; + uint64_t transforms; +}; + + +#endif /* SHA1_HPP */ Index: MicroBenchmarks/harris/sha1.cpp =================================================================== --- MicroBenchmarks/harris/sha1.cpp +++ MicroBenchmarks/harris/sha1.cpp @@ -0,0 +1,307 @@ +/* + sha1.cpp - source code of + + ============ + SHA-1 in C++ + ============ + + 100% Public Domain. + + Original C Code + -- Steve Reid + Small changes to fit into bglibs + -- Bruce Guenter + Translation to simpler C++ Code + -- Volker Diels-Grabsch + Safety fixes + -- Eugene Hopkinson +*/ + +#include "sha1.hpp" +#include +#include +#include + + +static const size_t BLOCK_INTS = 16; /* number of 32bit integers per SHA1 block */ +static const size_t BLOCK_BYTES = BLOCK_INTS * 4; + + +static void reset(uint32_t digest[], std::string &buffer, uint64_t &transforms) +{ + /* SHA1 initialization constants */ + digest[0] = 0x67452301; + digest[1] = 0xefcdab89; + digest[2] = 0x98badcfe; + digest[3] = 0x10325476; + digest[4] = 0xc3d2e1f0; + + /* Reset counters */ + buffer = ""; + transforms = 0; +} + + +static uint32_t rol(const uint32_t value, const size_t bits) +{ + return (value << bits) | (value >> (32 - bits)); +} + + +static uint32_t blk(const uint32_t block[BLOCK_INTS], const size_t i) +{ + return rol(block[(i+13)&15] ^ block[(i+8)&15] ^ block[(i+2)&15] ^ block[i], 1); +} + + +/* + * (R0+R1), R2, R3, R4 are the different operations used in SHA1 + */ + +static void R0(const uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i) +{ + z += ((w&(x^y))^y) + block[i] + 0x5a827999 + rol(v, 5); + w = rol(w, 30); +} + + +static void R1(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i) +{ + block[i] = blk(block, i); + z += ((w&(x^y))^y) + block[i] + 0x5a827999 + rol(v, 5); + w = rol(w, 30); +} + + +static void R2(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i) +{ + block[i] = blk(block, i); + z += (w^x^y) + block[i] + 0x6ed9eba1 + rol(v, 5); + w = rol(w, 30); +} + + +static void R3(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i) +{ + block[i] = blk(block, i); + z += (((w|x)&y)|(w&x)) + block[i] + 0x8f1bbcdc + rol(v, 5); + w = rol(w, 30); +} + + +static void R4(uint32_t block[BLOCK_INTS], const uint32_t v, uint32_t &w, const uint32_t x, const uint32_t y, uint32_t &z, const size_t i) +{ + block[i] = blk(block, i); + z += (w^x^y) + block[i] + 0xca62c1d6 + rol(v, 5); + w = rol(w, 30); +} + + +/* + * Hash a single 512-bit block. This is the core of the algorithm. + */ + +static void transform(uint32_t digest[], uint32_t block[BLOCK_INTS], uint64_t &transforms) +{ + /* Copy digest[] to working vars */ + uint32_t a = digest[0]; + uint32_t b = digest[1]; + uint32_t c = digest[2]; + uint32_t d = digest[3]; + uint32_t e = digest[4]; + + /* 4 rounds of 20 operations each. Loop unrolled. */ + R0(block, a, b, c, d, e, 0); + R0(block, e, a, b, c, d, 1); + R0(block, d, e, a, b, c, 2); + R0(block, c, d, e, a, b, 3); + R0(block, b, c, d, e, a, 4); + R0(block, a, b, c, d, e, 5); + R0(block, e, a, b, c, d, 6); + R0(block, d, e, a, b, c, 7); + R0(block, c, d, e, a, b, 8); + R0(block, b, c, d, e, a, 9); + R0(block, a, b, c, d, e, 10); + R0(block, e, a, b, c, d, 11); + R0(block, d, e, a, b, c, 12); + R0(block, c, d, e, a, b, 13); + R0(block, b, c, d, e, a, 14); + R0(block, a, b, c, d, e, 15); + R1(block, e, a, b, c, d, 0); + R1(block, d, e, a, b, c, 1); + R1(block, c, d, e, a, b, 2); + R1(block, b, c, d, e, a, 3); + R2(block, a, b, c, d, e, 4); + R2(block, e, a, b, c, d, 5); + R2(block, d, e, a, b, c, 6); + R2(block, c, d, e, a, b, 7); + R2(block, b, c, d, e, a, 8); + R2(block, a, b, c, d, e, 9); + R2(block, e, a, b, c, d, 10); + R2(block, d, e, a, b, c, 11); + R2(block, c, d, e, a, b, 12); + R2(block, b, c, d, e, a, 13); + R2(block, a, b, c, d, e, 14); + R2(block, e, a, b, c, d, 15); + R2(block, d, e, a, b, c, 0); + R2(block, c, d, e, a, b, 1); + R2(block, b, c, d, e, a, 2); + R2(block, a, b, c, d, e, 3); + R2(block, e, a, b, c, d, 4); + R2(block, d, e, a, b, c, 5); + R2(block, c, d, e, a, b, 6); + R2(block, b, c, d, e, a, 7); + R3(block, a, b, c, d, e, 8); + R3(block, e, a, b, c, d, 9); + R3(block, d, e, a, b, c, 10); + R3(block, c, d, e, a, b, 11); + R3(block, b, c, d, e, a, 12); + R3(block, a, b, c, d, e, 13); + R3(block, e, a, b, c, d, 14); + R3(block, d, e, a, b, c, 15); + R3(block, c, d, e, a, b, 0); + R3(block, b, c, d, e, a, 1); + R3(block, a, b, c, d, e, 2); + R3(block, e, a, b, c, d, 3); + R3(block, d, e, a, b, c, 4); + R3(block, c, d, e, a, b, 5); + R3(block, b, c, d, e, a, 6); + R3(block, a, b, c, d, e, 7); + R3(block, e, a, b, c, d, 8); + R3(block, d, e, a, b, c, 9); + R3(block, c, d, e, a, b, 10); + R3(block, b, c, d, e, a, 11); + R4(block, a, b, c, d, e, 12); + R4(block, e, a, b, c, d, 13); + R4(block, d, e, a, b, c, 14); + R4(block, c, d, e, a, b, 15); + R4(block, b, c, d, e, a, 0); + R4(block, a, b, c, d, e, 1); + R4(block, e, a, b, c, d, 2); + R4(block, d, e, a, b, c, 3); + R4(block, c, d, e, a, b, 4); + R4(block, b, c, d, e, a, 5); + R4(block, a, b, c, d, e, 6); + R4(block, e, a, b, c, d, 7); + R4(block, d, e, a, b, c, 8); + R4(block, c, d, e, a, b, 9); + R4(block, b, c, d, e, a, 10); + R4(block, a, b, c, d, e, 11); + R4(block, e, a, b, c, d, 12); + R4(block, d, e, a, b, c, 13); + R4(block, c, d, e, a, b, 14); + R4(block, b, c, d, e, a, 15); + + /* Add the working vars back into digest[] */ + digest[0] += a; + digest[1] += b; + digest[2] += c; + digest[3] += d; + digest[4] += e; + + /* Count the number of transformations */ + transforms++; +} + + +static void buffer_to_block(const std::string &buffer, uint32_t block[BLOCK_INTS]) +{ + /* Convert the std::string (byte buffer) to a uint32_t array (MSB) */ + for (size_t i = 0; i < BLOCK_INTS; i++) + { + block[i] = (buffer[4*i+3] & 0xff) + | (buffer[4*i+2] & 0xff)<<8 + | (buffer[4*i+1] & 0xff)<<16 + | (buffer[4*i+0] & 0xff)<<24; + } +} + + +SHA1::SHA1() +{ + reset(digest, buffer, transforms); +} + + +void SHA1::update(const std::string &s) +{ + std::istringstream is(s); + update(is); +} + + +void SHA1::update(std::istream &is) +{ + while (true) + { + char sbuf[BLOCK_BYTES]; + is.read(sbuf, BLOCK_BYTES - buffer.size()); + buffer.append(sbuf, is.gcount()); + if (buffer.size() != BLOCK_BYTES) + { + return; + } + uint32_t block[BLOCK_INTS]; + buffer_to_block(buffer, block); + transform(digest, block, transforms); + buffer.clear(); + } +} + + +/* + * Add padding and return the message digest. + */ + +std::string SHA1::final() +{ + /* Total number of hashed bits */ + uint64_t total_bits = (transforms*BLOCK_BYTES + buffer.size()) * 8; + + /* Padding */ + buffer += 0x80; + size_t orig_size = buffer.size(); + while (buffer.size() < BLOCK_BYTES) + { + buffer += (char)0x00; + } + + uint32_t block[BLOCK_INTS]; + buffer_to_block(buffer, block); + + if (orig_size > BLOCK_BYTES - 8) + { + transform(digest, block, transforms); + for (size_t i = 0; i < BLOCK_INTS - 2; i++) + { + block[i] = 0; + } + } + + /* Append total_bits, split this uint64_t into two uint32_t */ + block[BLOCK_INTS - 1] = total_bits; + block[BLOCK_INTS - 2] = (total_bits >> 32); + transform(digest, block, transforms); + + /* Hex std::string */ + std::ostringstream result; + for (size_t i = 0; i < sizeof(digest) / sizeof(digest[0]); i++) + { + result << std::hex << std::setfill('0') << std::setw(8); + result << digest[i]; + } + + /* Reset for next run */ + reset(digest, buffer, transforms); + + return result.str(); +} + + +std::string SHA1::from_file(const std::string &filename) +{ + std::ifstream stream(filename.c_str(), std::ios::binary); + SHA1 checksum; + checksum.update(stream); + return checksum.final(); +}