aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2024-12-12 21:21:29 -0700
committerJack Sangdahl <[email protected]>2024-12-12 21:21:29 -0700
commit3328ae7671fa7e329880ab002e8378b7ce851245 (patch)
treed45812276ec100ee76e1e995538ae1fc8f7ece95
parent5deaa39e8753469fe110820a152bc37c460f00fb (diff)
downloadcsci2400-3328ae7671fa7e329880ab002e8378b7ce851245.tar.gz
csci2400-3328ae7671fa7e329880ab002e8378b7ce851245.zip
Lab 4 Performance Lab
Signed-off-by: Jack Sangdahl <[email protected]>
-rw-r--r--lab4_perflab/Filter.cpp25
-rw-r--r--lab4_perflab/Filter.h23
-rw-r--r--lab4_perflab/FilterMain.cpp185
-rwxr-xr-xlab4_perflab/Judge92
-rw-r--r--lab4_perflab/Makefile56
-rw-r--r--lab4_perflab/README.md128
-rw-r--r--lab4_perflab/avg.filter5
-rw-r--r--lab4_perflab/blocks-small.bmpbin0 -> 3145782 bytes
-rw-r--r--lab4_perflab/boats.bmpbin0 -> 158538 bytes
-rw-r--r--lab4_perflab/cs1300bmp.cc1841
-rw-r--r--lab4_perflab/cs1300bmp.h48
-rw-r--r--lab4_perflab/edge.filter5
-rw-r--r--lab4_perflab/emboss.filter5
-rw-r--r--lab4_perflab/gauss.filter5
-rw-r--r--lab4_perflab/hline.filter5
-rw-r--r--lab4_perflab/optimisation.md83
-rw-r--r--lab4_perflab/rdtsc.h17
-rw-r--r--lab4_perflab/sharpen.filter5
-rw-r--r--lab4_perflab/tests/filtered-avg-blocks-small.bmpbin0 -> 3145782 bytes
-rw-r--r--lab4_perflab/tests/filtered-avg-boats.bmpbin0 -> 158538 bytes
-rw-r--r--lab4_perflab/tests/filtered-emboss-blocks-small.bmpbin0 -> 3145782 bytes
-rw-r--r--lab4_perflab/tests/filtered-emboss-boats.bmpbin0 -> 158538 bytes
-rw-r--r--lab4_perflab/tests/filtered-gauss-blocks-small.bmpbin0 -> 3145782 bytes
-rw-r--r--lab4_perflab/tests/filtered-gauss-boats.bmpbin0 -> 158538 bytes
-rw-r--r--lab4_perflab/tests/filtered-hline-blocks-small.bmpbin0 -> 3145782 bytes
-rw-r--r--lab4_perflab/tests/filtered-hline-boats.bmpbin0 -> 158538 bytes
-rw-r--r--lab4_perflab/vline.filter5
27 files changed, 2533 insertions, 0 deletions
diff --git a/lab4_perflab/Filter.cpp b/lab4_perflab/Filter.cpp
new file mode 100644
index 0000000..328a762
--- /dev/null
+++ b/lab4_perflab/Filter.cpp
@@ -0,0 +1,25 @@
+#include "Filter.h"
+#include <iostream>
+
+Filter::Filter(int _dim) {
+ divisor = 1;
+ dim = _dim;
+ data = new int[dim * dim];
+}
+
+inline int Filter::get(int r, int c) { return data[r * dim + c]; }
+
+void Filter::set(int r, int c, int value) { data[r * dim + c] = value; }
+
+void Filter::setDivisor(int value) { divisor = value; }
+
+void Filter::info() {
+ cout << "Filter is.." << endl;
+ for (int col = 0; col < dim; col++) {
+ for (int row = 0; row < dim; row++) {
+ int v = get(row, col);
+ cout << v << " ";
+ }
+ cout << endl;
+ }
+}
diff --git a/lab4_perflab/Filter.h b/lab4_perflab/Filter.h
new file mode 100644
index 0000000..5006762
--- /dev/null
+++ b/lab4_perflab/Filter.h
@@ -0,0 +1,23 @@
+//-*-c++-*-
+#ifndef _Filter_h_
+#define _Filter_h_
+
+using namespace std;
+
+class Filter {
+ int divisor;
+ int dim;
+ int *data;
+
+public:
+ Filter(int _dim);
+ inline int get(int r, int c);
+ void set(int r, int c, int value);
+
+ inline int getDivisor();
+ void setDivisor(int value);
+
+ void info();
+};
+
+#endif
diff --git a/lab4_perflab/FilterMain.cpp b/lab4_perflab/FilterMain.cpp
new file mode 100644
index 0000000..0d45dd6
--- /dev/null
+++ b/lab4_perflab/FilterMain.cpp
@@ -0,0 +1,185 @@
+#include "Filter.h"
+#include "cs1300bmp.h"
+#include <fstream>
+#include <iostream>
+#include <stdio.h>
+#include <stdlib.h>
+#include <omp.h>
+
+using namespace std;
+
+#include "rdtsc.h"
+
+inline int Filter::get(int r, int c) { return data[r * dim + c]; }
+
+inline int Filter::getDivisor() { return divisor; }
+
+//
+// Forward declare the functions
+//
+Filter *readFilter(string filename);
+double applyFilter(Filter *filter, cs1300bmp *input, cs1300bmp *output);
+
+int main(int argc, char **argv) {
+
+ if (argc < 2) {
+ fprintf(stderr, "Usage: %s filter inputfile1 inputfile2 .... \n", argv[0]);
+ }
+
+ //
+ // Convert to C++ strings to simplify manipulation
+ //
+ string filtername = argv[1];
+
+ //
+ // remove any ".filter" in the filtername
+ //
+ string filterOutputName = filtername;
+ string::size_type loc = filterOutputName.find(".filter");
+ if (loc != string::npos) {
+ //
+ // Remove the ".filter" name, which should occur on all the provided filters
+ //
+ filterOutputName = filtername.substr(0, loc);
+ }
+
+ Filter *filter = readFilter(filtername);
+
+ double sum = 0.0;
+ int samples = 0;
+
+ for (int inNum = 2; inNum < argc; inNum++) {
+ string inputFilename = argv[inNum];
+ string outputFilename =
+ "filtered-" + filterOutputName + "-" + inputFilename;
+ struct cs1300bmp *input = new struct cs1300bmp;
+ struct cs1300bmp *output = new struct cs1300bmp;
+ int ok = cs1300bmp_readfile((char *)inputFilename.c_str(), input);
+
+ if (ok) {
+ double sample = applyFilter(filter, input, output);
+ sum += sample;
+ samples++;
+ cs1300bmp_writefile((char *)outputFilename.c_str(), output);
+ }
+ delete input;
+ delete output;
+ }
+ fprintf(stdout, "Average cycles per sample is %f\n", sum / samples);
+}
+
+class Filter *readFilter(string filename) {
+ ifstream input(filename.c_str());
+
+ if (!input.bad()) {
+ int size = 0;
+ input >> size;
+ Filter *filter = new Filter(size);
+ int div;
+ input >> div;
+ filter->setDivisor(div);
+ for (int i = 0; i < size; i++) {
+ for (int j = 0; j < size; j++) {
+ int value;
+ input >> value;
+ filter->set(i, j, value);
+ }
+ }
+ return filter;
+ } else {
+ cerr << "Bad input in readFilter:" << filename << endl;
+ exit(-1);
+ }
+}
+
+double applyFilter(class Filter *filter, cs1300bmp *input, cs1300bmp *output) {
+
+ long long cycStart, cycStop;
+
+ cycStart = rdtscll();
+
+ int filter_divisor = filter->getDivisor();
+
+ int input_width = input->width;
+ int input_height = input->height;
+
+ int tmp1, tmp2; //accumulators
+ int col, j; //loop runners
+
+ //precalculate filtet.get() function calls
+ short filter_get[9], filter_idx = 0;
+ for (int i = 0; i < 3; i++)
+ for (int j = 0; j < 3; j++) {
+ filter_get[filter_idx] = filter->get(i, j);
+ filter_idx++;
+ }
+
+ output->width = input_width;
+ output->height = input_height;
+ #pragma omp parallel for
+ for (int plane = 0; plane < 3; plane++) {
+ for (int row = 1; row < input_height - 1; row++) {
+ for (col = 1; col < input_width - 2; col += 2) {
+ tmp1 = 0, tmp2 = 0, filter_idx = 0;
+ for (int i = 0; i < 3 ; i++) {
+ for (j = 0; j < 3 - 2; j += 3) {
+ tmp1 += (input->color[plane][row + i - 1][col + j - 1] * filter_get[filter_idx ])
+ + (input->color[plane][row + i - 1][col + j ] * filter_get[filter_idx + 1])
+ + (input->color[plane][row + i - 1][col + j + 1] * filter_get[filter_idx + 2]);
+ tmp2 += (input->color[plane][row + i - 1][col + j ] * filter_get[filter_idx ])
+ + (input->color[plane][row + i - 1][col + j + 1] * filter_get[filter_idx + 1])
+ + (input->color[plane][row + i - 1][col + j + 2] * filter_get[filter_idx + 2]);
+ filter_idx += 3;
+ }
+ for (; j < 3; j++) {
+ tmp1 += (input->color[plane][row + i - 1][col + j - 1] * filter_get[filter_idx]);
+ tmp2 += (input->color[plane][row + i - 1][col + j - 1] * filter_get[filter_idx]);
+ filter_idx++;
+ }
+ }
+ if (tmp1 < 0) {
+ output->color[plane][row][col] = 0;
+ } else if (tmp1 > filter_divisor * 255) {
+ output->color[plane][row][col] = 255;
+ } else {
+ output->color[plane][row][col] = tmp1 / filter_divisor;
+ }
+ if (tmp2 < 0) {
+ output->color[plane][row][col + 1] = 0;
+ } else if (tmp2 > filter_divisor * 255) {
+ output->color[plane][row][col + 1] = 255;
+ } else {
+ output->color[plane][row][col + 1] = tmp2 / filter_divisor;
+ }
+ }
+ for (; col < input_width - 1; col++) {
+ tmp1 = 0, filter_idx = 0;
+ for (int i = 0; i < 3 ; i++) {
+ for (j = 0; j < 3 - 2; j += 3) {
+ tmp1 += (input->color[plane][row + i - 1][col + j - 1] * filter_get[filter_idx ])
+ + (input->color[plane][row + i - 1][col + j ] * filter_get[filter_idx + 1])
+ + (input->color[plane][row + i - 1][col + j + 1] * filter_get[filter_idx + 2]);
+ filter_idx += 3;
+ }
+ for (; j < 3; j++) {
+ tmp1 += (input->color[plane][row + i - 1][col + j - 1] * filter_get[filter_idx]);
+ filter_idx++;
+ }
+ }
+ if (tmp1 < 0) {
+ output->color[plane][row][col] = 0;
+ } else if (tmp1 > filter_divisor * 255) {
+ output->color[plane][row][col] = 255;
+ } else {
+ output->color[plane][row][col] = tmp1 / filter_divisor;
+ }
+ }
+ }
+ }
+ cycStop = rdtscll();
+ double diff = cycStop - cycStart;
+ double diffPerPixel = diff / (output->width * output->height);
+ fprintf(stderr, "Took %f cycles to process, or %f cycles per pixel\n", diff,
+ diff / (output->width * output->height));
+ return diffPerPixel;
+}
diff --git a/lab4_perflab/Judge b/lab4_perflab/Judge
new file mode 100755
index 0000000..d7e4ebd
--- /dev/null
+++ b/lab4_perflab/Judge
@@ -0,0 +1,92 @@
+#!/usr/bin/perl
+#
+##
+## PerfLab judging script from 2011
+##
+## Usage:
+##
+## Judge [-l label] [-p program] [-i image] [-v] [-n #]
+##
+## This will run the program N times using the image specified.
+## Reasonable defaults are provide.
+##
+#
+use Getopt::Long;
+
+$image = "blocks-small.bmp";
+$program = $ENV{PROGRAM} || "filter";
+$samples = 6;
+$verbose = 0;
+$label = "";
+
+$result = GetOptions("program|p=s" => \$program,
+ "image|i=s" => \$image,
+ "label|l=s" => \$label,
+ "n=i" => \$samples,
+ "v" => \$verbose
+);
+
+if ( ! ($program =~ "\\..*" )) {
+ $program = "./$program";
+}
+-x $program || die "Unable to find executable program $program\n";
+-f $image || die "Unable to find image $image\n";
+if ( $samples < 4 ) {
+ printf "Warning - you won't get good results with -n $samples\n";
+}
+
+@FILTERS = ("gauss","avg","hline","emboss");
+
+@scores = ();
+
+for my $filter ( @FILTERS ){
+ if ( $verbose ) {
+ print "filter is $filter\n";
+ }
+ $cmd = "$program $filter.filter";
+ for (my $i = 0; $i < $samples; $i++) {
+ $cmd = "$cmd $image";
+ }
+
+ if ( $verbose ) {
+ printf "Run $cmd\n";
+ }
+
+ open(OUTPUT, "$cmd 2>&1 |") || die "Unable to run $cmd\n";
+
+ printf "$filter: ";
+ while (<OUTPUT>) {
+ if (/or ([0-9\.]+) cycles/) {
+ print $1, "..";
+ push(@scores, int($1));
+ }
+ }
+ printf "\n";
+ close(OUTPUT);
+}
+@scores = sort { int($a) <=> int($b) } @scores;
+print "Scores are @scores \n";
+$median = int( ($#scores + 1) / 2 );
+$cpe = $scores[$median];
+
+if ($label =~ "") {
+ print "median CPE is ", $cpe, "\n";
+} else {
+ print "median CPE for $label is ", $cpe, "\n";
+}
+
+if ($cpe > 400) {
+ $score = 0;
+} else {
+ $score = 123.9 + $cpe * (-0.010193) + -3.369452*sqrt($cpe) + 5;
+ if ($score > 110 ) {
+ $score = 110;
+ }
+}
+$score = int($score);
+
+if ($label =~ "") {
+ print "Resulting score is $score\n";
+} else {
+ print "Resulting score for $label is $score\n";
+}
diff --git a/lab4_perflab/Makefile b/lab4_perflab/Makefile
new file mode 100644
index 0000000..a0f2acb
--- /dev/null
+++ b/lab4_perflab/Makefile
@@ -0,0 +1,56 @@
+##
+##
+
+CXX =g++
+##
+## Use our standard compiler flags for the course...
+## You can try changing these flags to improve performance.
+##
+CXXFLAGS= -g -O3 -fno-omit-frame-pointer -Wall -fopenmp
+
+goals: filter judge
+ @echo "Done"
+
+filter: FilterMain.cpp Filter.cpp cs1300bmp.cc cs1300bmp.h Filter.h rdtsc.h
+ $(CXX) $(CXXFLAGS) -o filter FilterMain.cpp Filter.cpp cs1300bmp.cc
+
+##
+## Parameters for the test run
+##
+FILTERS = gauss.filter vline.filter hline.filter emboss.filter
+IMAGES = boats.bmp blocks-small.bmp
+TRIALS = 1 2 3 4
+
+#
+# Run the Judge script to compute a score
+#
+judge: filter
+ @echo Running run for performance / scoring information
+ ./Judge -p ./filter -i blocks-small.bmp
+ @echo Now checking if the output is correct. Any errors indicate bugs in your code.
+ @cmp filtered-avg-blocks-small.bmp tests/filtered-avg-blocks-small.bmp
+ @cmp filtered-emboss-blocks-small.bmp tests/filtered-emboss-blocks-small.bmp
+ @cmp filtered-gauss-blocks-small.bmp tests/filtered-gauss-blocks-small.bmp
+ @cmp filtered-hline-blocks-small.bmp tests/filtered-hline-blocks-small.bmp
+
+#
+# Run the Judge tests on both images and then compare the output to the reference output.
+#
+# Note you shouldn't use this to compute a score -- it's just for testing
+#
+test: filter
+ ./Judge -p ./filter -i boats.bmp
+ ./Judge -p ./filter -i blocks-small.bmp
+ cmp filtered-avg-blocks-small.bmp tests/filtered-avg-blocks-small.bmp
+ cmp filtered-avg-boats.bmp tests/filtered-avg-boats.bmp
+ cmp filtered-emboss-blocks-small.bmp tests/filtered-emboss-blocks-small.bmp
+ cmp filtered-emboss-boats.bmp tests/filtered-emboss-boats.bmp
+ cmp filtered-gauss-blocks-small.bmp tests/filtered-gauss-blocks-small.bmp
+ cmp filtered-gauss-boats.bmp tests/filtered-gauss-boats.bmp
+ cmp filtered-hline-blocks-small.bmp tests/filtered-hline-blocks-small.bmp
+ @echo All tests passed
+
+clean:
+ -rm -f *.o
+ -rm -f filter
+ -rm -f filtered-*.bmp
diff --git a/lab4_perflab/README.md b/lab4_perflab/README.md
new file mode 100644
index 0000000..364f3d1
--- /dev/null
+++ b/lab4_perflab/README.md
@@ -0,0 +1,128 @@
+[![Open in Codespaces](https://classroom.github.com/assets/launch-codespace-f4981d0f882b2a3f0472912d15f9806d57e124e0fc890972558857b51b24a6f9.svg)](https://classroom.github.com/open-in-codespaces?assignment_repo_id=10400982)
+# Lab 4 - Code Optimization
+## Introduction
+This assignment deals with optimizing memory intensive code. Image processing offers many examples of functions that can benefit from optimization. In this lab, you’ll be improving the overall performance of an “image processing” application by a factor of about 25 – an extra credit phase will challenge you do increase the speed further. In the past, some students have sped up the code by a factor of 200-300. The score you receive for the "performance" portion of the lab depends on the score returned by the **Judge** script with the filters for the default image (blocks-small.bmp). Your code **must** function correctly for each filter and can be tested using `make test`
+
+The application you’ll be modifying reads in an “image” (a picture) and a “filter”. An image is represented as a three-dimensional array, described in [cs1300bmp.h](cs1300bmp.h). Each pixel is represented as a combination of (red, green, blue) values. When coded in the BMP picture format, the individual (R,G,B) values can taken on the values 0...255, but the `cs1300bmp.h` code is designed to handle larger pixel values. The code in `cs1300bmp.cpp` provides routines for reading and writing images in the BMP format. **You are free to modify the format or the layout of the data structures in that code.**
+
+The “filter” is an n x n array of numbers. We’ll go through the logistics of how a “filter” works in recitation and in class and briefly summarize it here. Basically, you can cause a number of visual affects by applying a filter to an image. The filter is implemented as a *convolution*, which means that elements of the filter matrix are multiplied by the image matrix to compute a new value for the image. Pictorially, this is represented as:
+
+![Filter Description](writeup-image.png)
+
+Computationally, this is structured as five nested `for` loops (three to go over the colors, row and columns and two more to apply the filter). In the solution provided to you, filters are represented using the `Filter` class, implemented in `Filter.h` and `Filter.cpp`.
+
+The majority of the work performed by the filter application is in the routine shown below:
+
+```
+ long long cycStart, cycStop;
+ rdtscll(cycStart);
+
+ output -> width = input -> width;
+ output -> height = input -> height;
+
+ for(int col = 1; col < (input -> width) - 1; col = col + 1) {
+ for(int row = 1; row < (input -> height) - 1 ; row = row + 1) {
+ for(int plane = 0; plane < 3; plane++) {
+ output -> color[plane][row][col] = 0;
+ for (int j = 0; j < filter -> getSize(); j++) {
+ for (int i = 0; i < filter -> getSize(); i++) {
+ output -> color[plane][row][col] = output -> color[plane][row][col]
+ + input -> color[plane][row + i - 1][col + j - 1] * filter -> get(i, j);
+ }
+ }
+ output -> color[plane][row][col]
+ = output -> color[plane][row][col] / filter -> getDivisor();
+ if ( output -> color[plane][row][col] < 0 ) { output -> color[plane][row][col] = 0; }
+ if ( output -> color[plane][row][col] > 255 ) { output -> color[plane][row][col] = 255; }
+ output -> color[plane][row][col] = output -> color[plane][row][col];
+ }
+ }
+ }
+ rdtscll(cycStop);
+ double diff = cycStop - cycStart;
+ fprintf(stderr, "Took %f cycles to process, or %f cycles per pixel\n",
+ diff, diff / (output -> width * output -> height));
+```
+This routine is “instrumented” using the `rdscll` function. This inline function records the starting and finish times in terms of CPU cycles. We use this to determine the “cycles per element” needed to apply the filter to a given image. A sample of the output for the provided setup code looks like the following when run:
+
+```
+Took 170624720.000000 cycles to process, or 3229.816007 cycles per pixel
+```
+
+The cycle counter measures times using the CPU clock of your computer. It is fairly accurate, but many things (such as other running programs) influence the reported time. Thus, we will use the *median* of a number of runs to determine the time for a particular implementation of the program for a number of different filters.
+`
+Your job is going to be to improve the performance of this application using techniques detailed in Chapter 5 of the text. You’ll be using two images ([boats.bmp](boats.bmp) and [blocks-small.bmp](blocks-small.bmp)) The first image is fairly small (useful for quickly testing ideas) and the second image is larger (and used for grading / evaluation). You can run your program using a command line similar to this:
+
+```
+$ filter hline.filter boats.bmp
+```
+
+This invocation will leave the output image in `filter-hline-boats.bmp` and will report the time taken, as in the examples above. You can repeat the image name (or use different images) on the same command line to run the filter multiple times & return the average. For example:
+
+```
+$ ./filter hline.filter boats.bmp boats.bmp
+Took 139255936.000000 cycles to process, or 2636.025138 cycles per pixel
+Took 137527184.000000 cycles to process, or 2603.300977 cycles per pixel
+Average cycles per sample is 2619.663057
+```
+
+## Performance and Correctness
+
+We’ll be using a script called `Judge` to score your program. The `Judge` program takes three optional arguments.
+* `-n` specifies the number of times each filter should be executed,
+* `-i` specifies the image file and,
+* `-p` specifies the program name.
+
+The default options are shown explicitly in the following example.
+
+```
+% make
+g++ -m32 -g -O0 -fno-omit-frame-pointer -o filter FilterMain.cpp Filter.cpp cs1300b
+./Judge -p ./filter -i blocks-small.bmp
+gauss: 4003.824003..4038.171866..3872.371058..3990.658428..3931.838805..4319.173193
+avg: 3807.727624..3822.502626..3962.588553..4237.542068..4322.871861..4056.862357..
+hline: 4171.320541..4234.822551..3851.320030..4385.223120..4366.434546..4422.357822
+emboss: 3694.797139..3924.230283..3927.254491..4309.121033..3981.110480..3990.70275
+Scores are 3694 3807 3822 3851 3872 3924 3927 3931 3962 3981 3990 3990 4003 4038 40
+median CPE for is 4003
+Resulting score for is 0
+echo "Done"
+Done
+```
+
+This would result in an average of 4003 cycles per second. Scoring is based on the a function based on the CPE for the `blocks-small.bmp` image running on the GitHub Actions. In other words, the GitHub Actions is being the source of truth for grading.
+
+The provided `Makefile` compiles your program; **you may need to modify it to change compiler options or the like**. We assume you are compiling your program on the https://coding.csel.io machines. You are free to use different compiler options if you think that will help and know how. You can read more about the GCC options at http://gcc.gnu.org/onlinedocs/gcc-4.4.2/gcc/i386-and-x86_002d64-Options.html. You can also use the clang compiler (clang++) if you think that will help.
+
+The `Makefile` includes a target make test that compares your output to the reference solution. Run make test frequently, because it’s easy to accidentally break the code when trying to optimize. Your code must be correct as well as quick.
+
+The Makefile also provides a make judge rule that runs the test images and filters. Lastly, it provides a `make clean` rule to delete any temporary files or images.
+
+Your measured time needs to include any active processing you do to the image after it is read in and before it is written out. You’re free to go “whole hog” on any optimization that might work, as long as it works with all the test images and filters included in the assignment. Your modified code does not need to handle any filters or images not included in the evaluation suite. This means you can go ahead and e.g change the matrix layout in the BMP image library, replace the Filter library, etc. However, you’d be well advised to make certain those changes are important and effective before you sink a lot of time.
+
+## Extra Credit
+The most “extreme” solution is to use SIMD extensions such as MMX, SSE, SSE2 or SSE3. See http:// jeffmatherphotography.com/dispatches/2012/02/an-experiment-with-sse/ for more information.
+
+For this lab, the CSCI 2400 machines will also each have multiple CPU’s or cores and you could use the OpenMP language extensions (see http://bisqwit.iki.fi/story/howto/openmp/ to try to use both cores. This is an easy thing to do, but hard to get big speedup.
+
+Alternative, you can take advantage of the sk1llz of other l33t h4x0rs and use a libary like the “Open Computer Vision” library, [OpenCV](http://docs.opencv.org/modules/imgproc/doc/filtering.html?highlight=filter2d#filter2d). This is complicated because you have to get your image into their data structure format and you need to include the time to get it into that format in your timing.
+
+One year, one student (who later interned for Google) got a CPE of about 20ish. Another year, another student (who later interned for Apple) for a CPE of about 3-4.
+
+Some students have used these methods in the past, but you’re well advised to go for the easy low-hanging fruit before tackling the most aggressive optimization.
+
+If you come up with a solution that uses OpenMP, you’ll get up to an additional 5 points extra credit. If you come up with a solution using SSE/vectors, you’ll get up to 10 points extra credit (assuming your changes result in faster code and you know why) and likewise switching to OpenCV is good for 10 points of extra credit. In each case, you’ll have to know what you did and why it works like always.
+
+## Logistics
+The only “hand-in” will be electronic through your GitHub repo. Any clarifications and revisions to the assignment will be posted on the course Web page.
+
+Different computers will run this code at different speeds (even measured in “cycles per second”). In order to have a level playing field, everyone must use the CSCI 2400 machines on the https://coding.csel.io platform to time their projects.
+
+Since it’s usually true that making something run faster on one machine makes it run faster on another, you might be able to do your development on one machine and then use the https://coding.csel.io machines simply to validate your measurements or improvements.
+
+## Grading
+You must commit and push your changes to github by the due date. That is the only mechanism for handing in your solution.
+
+The score calculated by running the program provides 40% of the total score. You need to be able to explain why your code modifications improve the running time for the program and explain what would happen with minor modifications for the other 60%.
+
+Again, you must be able to explain *why* you got the performance you did, so you should take notes for why you made each modification to bring to your grading meetings.
diff --git a/lab4_perflab/avg.filter b/lab4_perflab/avg.filter
new file mode 100644
index 0000000..6427873
--- /dev/null
+++ b/lab4_perflab/avg.filter
@@ -0,0 +1,5 @@
+3
+9
+1 1 1
+1 1 1
+1 1 1
diff --git a/lab4_perflab/blocks-small.bmp b/lab4_perflab/blocks-small.bmp
new file mode 100644
index 0000000..9ecdf34
--- /dev/null
+++ b/lab4_perflab/blocks-small.bmp
Binary files differ
diff --git a/lab4_perflab/boats.bmp b/lab4_perflab/boats.bmp
new file mode 100644
index 0000000..91e1474
--- /dev/null
+++ b/lab4_perflab/boats.bmp
Binary files differ
diff --git a/lab4_perflab/cs1300bmp.cc b/lab4_perflab/cs1300bmp.cc
new file mode 100644
index 0000000..468e62c
--- /dev/null
+++ b/lab4_perflab/cs1300bmp.cc
@@ -0,0 +1,1841 @@
+#include <cstdlib>
+#include <fstream>
+#include <iomanip>
+#include <iostream>
+
+using namespace std;
+
+extern "C" {
+#include "cs1300bmp.h"
+}
+
+//
+// Forward decl's
+//
+static bool bmp_08_data_read(ifstream &file_in, unsigned long int width,
+ long int height, unsigned char *rarray);
+
+static bool bmp_24_data_read(ifstream &file_in, unsigned long int width,
+ long int height, unsigned char *rarray,
+ unsigned char *garray, unsigned char *barray);
+static void bmp_24_data_write(ofstream &file_out, unsigned long int width,
+ long int height, unsigned char *rarray,
+ unsigned char *garray, unsigned char *barray);
+
+static bool bmp_header2_read(
+ ifstream &file_in, unsigned long int *size, unsigned long int *width,
+ long int *height, unsigned short int *planes,
+ unsigned short int *bitsperpixel, unsigned long int *compression,
+ unsigned long int *sizeofbitmap, unsigned long int *horzresolution,
+ unsigned long int *vertresolution, unsigned long int *colorsused,
+ unsigned long int *colorsimportant);
+static void bmp_header2_write(
+ ofstream &file_out, unsigned long int size, unsigned long int width,
+ long int height, unsigned short int planes, unsigned short int bitsperpixel,
+ unsigned long int compression, unsigned long int sizeofbitmap,
+ unsigned long int horzresolution, unsigned long int vertresolution,
+ unsigned long int colorsused, unsigned long int colorsimportant);
+
+static bool bmp_palette_read(ifstream &file_in, unsigned long int colorsused,
+ unsigned char *rparray, unsigned char *gparray,
+ unsigned char *bparray, unsigned char *aparray);
+static void bmp_palette_write(ofstream &file_out, unsigned long int colorsused,
+ unsigned char *rparray, unsigned char *gparray,
+ unsigned char *bparray, unsigned char *aparray);
+
+static bool bmp_read(char *file_in_name, unsigned long int *width,
+ long int *height, unsigned char **rarray,
+ unsigned char **garray, unsigned char **barray);
+
+static bool bmp_24_write(char *file_out_name, unsigned long int width,
+ long int height, unsigned char *rarray,
+ unsigned char *garray, unsigned char *barray);
+
+static bool long_int_read(long int *long_int_val, ifstream &file_in);
+static void long_int_write(long int long_int_val, ofstream &file_out);
+
+static bool u_long_int_read(unsigned long int *u_long_int_val,
+ ifstream &file_in);
+static void u_long_int_write(unsigned long int u_long_int_val,
+ ofstream &file_out);
+
+static bool u_short_int_read(unsigned short int *u_short_int_val,
+ ifstream &file_in);
+static void u_short_int_write(unsigned short int u_short_int_val,
+ ofstream &file_out);
+
+//
+// BMP_BYTE_SWAP controls how the program assumes that the bytes in
+// multi-byte data are ordered.
+//
+// "true" is the correct value to use when running on a little-endian machine,
+// and "false" is for big-endian.
+//
+
+static bool bmp_byte_swap = true;
+
+//****************************************************************************
+
+//****************************************************************************
+
+static bool bmp_08_data_read(ifstream &file_in, unsigned long int width,
+ long int height, unsigned char *rarray)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_08_DATA_READ reads 8 bit image data of the BMP file.
+//
+// Discussion:
+//
+// On output, the RGB information in the file has been copied into the
+// R, G and B arrays.
+//
+// Thanks to Peter Kionga-Kamau for pointing out an error in the
+// previous implementation.
+//
+// The standard ">>" operator cannot be used to transfer data, because
+// it will be deceived by characters that "look like" new lines.
+//
+// Thanks to Kelly Anderson for pointing out that the program did not handle
+// monochrome images, but could easily be modified to do so.
+//
+// Modified:
+//
+// 01 April 2005
+//
+// Author:
+//
+// Kelly Anderson
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Input, unsigned long int WIDTH, the X dimension of the image.
+//
+// Input, long int HEIGHT, the Y dimension of the image.
+//
+// Input, unsigned char *RARRAY, a pointer to the red color arrays.
+//
+// Output, bool BMP_08_DATA_READ, is true if an error occurred.
+//
+{
+ char c;
+ bool error;
+ unsigned char *indexr;
+ int numbyte;
+ int padding;
+ //
+ // Set the padding.
+ //
+ padding = (4 - ((1 * width) % 4)) % 4;
+
+ indexr = rarray;
+ numbyte = 0;
+
+ for (int j = 0; j < abs(height); j++) {
+ for (unsigned int i = 0; i < width; i++) {
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_08_DATA_READ: Fatal error!\n";
+ cout << " Failed reading R for pixel (" << i << "," << j << ").\n";
+ return error;
+ }
+
+ *indexr = (unsigned char)c;
+ numbyte = numbyte + 1;
+ indexr = indexr + 1;
+ }
+ //
+ // If necessary, read a few padding characters.
+ //
+ for (int i = 0; i < padding; i++) {
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_08_DATA_READ - Warning!\n";
+ cout << " Failed while reading padding character " << i << "\n";
+ cout << " of total " << padding << " characters\n";
+ cout << " at the end of line " << j << "\n";
+ cout << "\n";
+ cout << " This is a minor error.\n";
+ return false;
+ }
+ }
+ }
+
+ return false;
+}
+
+static bool bmp_24_data_read(ifstream &file_in, unsigned long int width,
+ long int height, unsigned char *rarray,
+ unsigned char *garray, unsigned char *barray)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_24_DATA_READ reads 24 bit image data of the BMP file.
+//
+// Discussion:
+//
+// On output, the RGB information in the file has been copied into the
+// R, G and B arrays.
+//
+// Thanks to Peter Kionga-Kamau for pointing out an error in the
+// previous implementation.
+//
+// The standard ">>" operator cannot be used to transfer data, because
+// it will be deceived by characters that "look like" new lines.
+//
+// Modified:
+//
+// 11 December 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Input, unsigned long int WIDTH, the X dimension of the image.
+//
+// Input, long int HEIGHT, the Y dimension of the image.
+//
+// Input, unsigned char *RARRAY, *GARRAY, *BARRAY, pointers to the
+// red, green and blue color arrays.
+//
+// Output, bool BMP_24_DATA_READ, is true if an error occurred.
+//
+{
+ char c;
+ bool error;
+ unsigned char *indexb;
+ unsigned char *indexg;
+ unsigned char *indexr;
+ int numbyte;
+ int padding;
+ //
+ // Set the padding.
+ //
+ padding = (4 - ((3 * width) % 4)) % 4;
+
+ indexr = rarray;
+ indexg = garray;
+ indexb = barray;
+ numbyte = 0;
+
+ for (int j = 0; j < abs(height); j++) {
+ for (unsigned int i = 0; i < width; i++) {
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_24_DATA_READ: Fatal error!\n";
+ cout << " Failed reading B for pixel (" << i << "," << j << ").\n";
+ return error;
+ }
+
+ *indexb = (unsigned char)c;
+ numbyte = numbyte + 1;
+ indexb = indexb + 1;
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_24_DATA_READ: Fatal error!\n";
+ cout << " Failed reading G for pixel (" << i << "," << j << ").\n";
+ return error;
+ }
+
+ *indexg = (unsigned char)c;
+ numbyte = numbyte + 1;
+ indexg = indexg + 1;
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_24_DATA_READ: Fatal error!\n";
+ cout << " Failed reading R for pixel (" << i << "," << j << ").\n";
+ return error;
+ }
+
+ *indexr = (unsigned char)c;
+ numbyte = numbyte + 1;
+ indexr = indexr + 1;
+ }
+ //
+ // If necessary, read a few padding characters.
+ //
+ for (int i = 0; i < padding; i++) {
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_24_DATA_READ - Warning!\n";
+ cout << " Failed while reading padding character " << i << "\n";
+ cout << " of total " << padding << " characters\n";
+ cout << " at the end of line " << j << "\n";
+ cout << "\n";
+ cout << " This is a minor error.\n";
+ return false;
+ }
+ }
+ }
+
+ return false;
+}
+//****************************************************************************
+
+static void bmp_24_data_write(ofstream &file_out, unsigned long int width,
+ long int height, unsigned char *rarray,
+ unsigned char *garray, unsigned char *barray)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_24_DATA_WRITE writes 24 bit image data to the BMP file.
+//
+// Discussion:
+//
+// The BMP format requires that each horizontal line be a multiple of 4
+// bytes. If the data itself does not have a WIDTH that is a multiple of 4,
+// then the file must be padded with a few extra bytes so that each line has
+// the appropriate length. This information, and the corresponding
+// corrective code, was supplied by Lee Mulcahy.
+//
+// Modified:
+//
+// 11 December 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ofstream &FILE_OUT, a reference to the output file.
+//
+// Input, unsigned long int WIDTH, the X dimension of the image in bytes.
+//
+// Input, long int HEIGHT, the Y dimension of the image in bytes.
+//
+// Input, unsigned char *RARRAY, *GARRAY, *BARRAY, pointers to the red, green
+// and blue color arrays.
+//
+{
+ unsigned char *indexb;
+ unsigned char *indexg;
+ unsigned char *indexr;
+ int padding;
+ //
+ // Set the padding.
+ //
+ padding = (4 - ((3 * width) % 4)) % 4;
+
+ indexr = rarray;
+ indexg = garray;
+ indexb = barray;
+
+ for (int j = 0; j < abs(height); j++) {
+ for (unsigned int i = 0; i < width; i++) {
+ file_out << *indexb;
+ file_out << *indexg;
+ file_out << *indexr;
+
+ indexb = indexb + 1;
+ indexg = indexg + 1;
+ indexr = indexr + 1;
+ }
+
+ for (int i = 0; i < padding; i++) {
+ file_out << 0;
+ }
+ }
+
+ return;
+}
+//****************************************************************************
+
+bool bmp_header1_read(ifstream &file_in, unsigned short int *filetype,
+ unsigned long int *filesize,
+ unsigned short int *reserved1,
+ unsigned short int *reserved2,
+ unsigned long int *bitmapoffset)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_HEADER1_READ reads the header information of a BMP file.
+//
+// Discussion:
+//
+// The header comprises 14 bytes:
+//
+// 2 bytes FILETYPE; Magic number: "BM",
+// 4 bytes FILESIZE; Size of file in 32 byte integers,
+// 2 bytes RESERVED1; Always 0,
+// 2 bytes RESERVED2; Always 0,
+// 4 bytes BITMAPOFFSET. Starting position of image data, in bytes.
+//
+// Modified:
+//
+// 15 December 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Output, unsigned short int *FILETYPE, the file type.
+//
+// Output, unsigned long int *FILESIZE, the file size.
+//
+// Output, unsigned short int *RESERVED1, a reserved value.
+//
+// Output, unsigned short int *RESERVED2, a reserved value.
+//
+// Output, unsigned long int *BITMAPOFFSET, the bitmap offset.
+//
+{
+ bool error;
+ char i1;
+ char i2;
+ //
+ // Read FILETYPE.
+ //
+ error = u_short_int_read(filetype, file_in);
+
+ if (error) {
+ return error;
+ }
+ //
+ // If you are doing swapping, you have to reunswap the filetype, I think, JVB
+ // 15 December 2004.
+ //
+ if (bmp_byte_swap) {
+ i1 = (char)(*filetype / 256);
+ i2 = (char)(*filetype % 256);
+ *filetype = i2 * 256 + i1;
+ }
+ //
+ // Read FILESIZE.
+ //
+ error = u_long_int_read(filesize, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read RESERVED1.
+ //
+ error = u_short_int_read(reserved1, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read RESERVED2.
+ //
+ error = u_short_int_read(reserved2, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read BITMAPOFFSET.
+ //
+ error = u_long_int_read(bitmapoffset, file_in);
+ if (error) {
+ return error;
+ }
+
+ error = false;
+ return error;
+}
+//****************************************************************************
+
+void bmp_header1_write(ofstream &file_out, unsigned short int filetype,
+ unsigned long int filesize, unsigned short int reserved1,
+ unsigned short int reserved2,
+ unsigned long int bitmapoffset)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_HEADER1_WRITE writes the header information to a BMP file.
+//
+// Discussion:
+//
+// The header comprises 14 bytes:
+//
+// 2 bytes FILETYPE; Magic number: "BM",
+// 4 bytes FILESIZE; Size of file in 32 byte integers,
+// 2 bytes RESERVED1; Always 0,
+// 2 bytes RESERVED2; Always 0,
+// 4 bytes BITMAPOFFSET. Starting position of image data, in bytes.
+//
+// Modified:
+//
+// 04 March 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ofstream &FILE_OUT, a reference to the output file.
+//
+// Input, unsigned short int FILETYPE, the file type.
+//
+// Input, unsigned long int FILESIZE, the file size.
+//
+// Input, unsigned short int RESERVED1, a reserved value.
+//
+// Input, unsigned short int RESERVED2, a reserved value.
+//
+// Input, unsigned long int BITMAPOFFSET, the bitmap offset.
+//
+{
+ u_short_int_write(filetype, file_out);
+ u_long_int_write(filesize, file_out);
+ u_short_int_write(reserved1, file_out);
+ u_short_int_write(reserved2, file_out);
+ u_long_int_write(bitmapoffset, file_out);
+
+ return;
+}
+//****************************************************************************
+
+static bool bmp_header2_read(
+ ifstream &file_in, unsigned long int *size, unsigned long int *width,
+ long int *height, unsigned short int *planes,
+ unsigned short int *bitsperpixel, unsigned long int *compression,
+ unsigned long int *sizeofbitmap, unsigned long int *horzresolution,
+ unsigned long int *vertresolution, unsigned long int *colorsused,
+ unsigned long int *colorsimportant)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_HEADER2_READ reads the bitmap header information of a BMP file.
+//
+// Discussion:
+//
+// The bitmap header is 40 bytes long:
+//
+// 4 bytes SIZE; Size of this header, in bytes.
+// 4 bytes WIDTH; Image width, in pixels.
+// 4 bytes HEIGHT; Image height, in pixels.
+// (Pos/Neg, origin at bottom, top)
+// 2 bytes PLANES; Number of color planes (always 1).
+// 2 bytes BITSPERPIXEL; 1 to 24. 1, 4, 8, 16, 24 or 32.
+// 4 bytes COMPRESSION; 0, uncompressed; 1, 8 bit RLE;
+// 2, 4 bit RLE; 3, bitfields.
+// 4 bytes SIZEOFBITMAP; Size of bitmap in bytes. (0 if uncompressed).
+// 4 bytes HORZRESOLUTION; Pixels per meter. (Can be zero)
+// 4 bytes VERTRESOLUTION; Pixels per meter. (Can be zero)
+// 4 bytes COLORSUSED; Number of colors in palette. (Can be zero).
+// 4 bytes COLORSIMPORTANT. Minimum number of important colors. (Can be
+// zero).
+//
+// Modified:
+//
+// 03 March 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Output, unsigned long int *SIZE, the size of this header in bytes.
+//
+// Output, unsigned long int *WIDTH, the X dimension of the image.
+//
+// Output, long int *HEIGHT, the Y dimension of the image.
+//
+// Output, unsigned short int *PLANES, the number of color planes.
+//
+// Output, unsigned short int *BITSPERPIXEL, color bits per pixel.
+//
+// Output, unsigned long int *COMPRESSION, the compression option.
+//
+// Output, unsigned long int *SIZEOFBITMAP, the size of the bitmap.
+//
+// Output, unsigned long int *HORZRESOLUTION, the horizontal resolution.
+//
+// Output, unsigned long int *VERTRESOLUTION, the vertical resolution.
+//
+// Output, unsigned long int *COLORSUSED, the number of colors in the
+// palette.
+//
+// Output, unsigned long int *COLORSIMPORTANT, the minimum number of colors.
+//
+// Output, bool BMP_HEADER2_READ, is true if an error occurred.
+//
+{
+ bool error;
+ //
+ // Read SIZE, the size of the header in bytes.
+ //
+ error = u_long_int_read(size, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read WIDTH, the image width in pixels.
+ //
+ error = u_long_int_read(width, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read HEIGHT, the image height in pixels.
+ //
+ error = long_int_read(height, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read PLANES, the number of color planes.
+ //
+ error = u_short_int_read(planes, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read BITSPERPIXEL.
+ //
+ error = u_short_int_read(bitsperpixel, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read COMPRESSION.
+ //
+ error = u_long_int_read(compression, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read SIZEOFBITMAP.
+ //
+ error = u_long_int_read(sizeofbitmap, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read HORZRESOLUTION.
+ //
+ error = u_long_int_read(horzresolution, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read VERTRESOLUTION.
+ //
+ error = u_long_int_read(vertresolution, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read COLORSUSED.
+ //
+ error = u_long_int_read(colorsused, file_in);
+ if (error) {
+ return error;
+ }
+ //
+ // Read COLORSIMPORTANT.
+ //
+ error = u_long_int_read(colorsimportant, file_in);
+ if (error) {
+ return error;
+ }
+
+ error = false;
+ return error;
+}
+//****************************************************************************
+
+static void bmp_header2_write(
+ ofstream &file_out, unsigned long int size, unsigned long int width,
+ long int height, unsigned short int planes, unsigned short int bitsperpixel,
+ unsigned long int compression, unsigned long int sizeofbitmap,
+ unsigned long int horzresolution, unsigned long int vertresolution,
+ unsigned long int colorsused, unsigned long int colorsimportant)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_HEADER2_WRITE writes the bitmap header information to a BMP file.
+//
+// Discussion:
+//
+// Thanks to Mark Cave-Ayland, [email protected], for pointing out an
+// error which caused the code to write one too many long ints, 19 May 2001.
+//
+// The bitmap header is 40 bytes long:
+//
+// 4 bytes SIZE; Size of this header, in bytes.
+// 4 bytes WIDTH; Image width, in pixels.
+// 4 bytes HEIGHT; Image height, in pixels.
+// (Pos/Neg, origin at bottom, top)
+// 2 bytes PLANES; Number of color planes (always 1).
+// 2 bytes BITSPERPIXEL; 1 to 24. 1, 4, 8, 16, 24 or 32.
+// 4 bytes COMPRESSION; 0, uncompressed; 1, 8 bit RLE;
+// 2, 4 bit RLE; 3, bitfields.
+// 4 bytes SIZEOFBITMAP; Size of bitmap in bytes. (0 if uncompressed).
+// 4 bytes HORZRESOLUTION; Pixels per meter. (Can be zero)
+// 4 bytes VERTRESOLUTION; Pixels per meter. (Can be zero)
+// 4 bytes COLORSUSED; Number of colors in palette. (Can be zero).
+// 4 bytes COLORSIMPORTANT. Minimum number of important colors. (Can be
+// zero).
+//
+// Modified:
+//
+// 03 March 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ofstream &FILE_OUT, a reference to the output file.
+//
+// Input, unsigned long int SIZE, the size of this header in bytes.
+//
+// Input, unsigned long int WIDTH, the X dimensions of the image.
+//
+// Input, long int HEIGHT, the Y dimensions of the image.
+//
+// Input, unsigned short int PLANES, the number of color planes.
+//
+// Input, unsigned short int BITSPERPIXEL, color bits per pixel.
+//
+// Input, unsigned long int COMPRESSION, the compression option.
+//
+// Input, unsigned long int SIZEOFBITMAP, the size of the bitmap.
+//
+// Input, unsigned long int HORZRESOLUTION, the horizontal resolution.
+//
+// Input, unsigned long int VERTRESOLUTION, the vertical resolution.
+//
+// Input, unsigned long int COLORSUSED, the number of colors in the palette.
+//
+// Input, unsigned long int COLORSIMPORTANT, the minimum number of colors.
+//
+{
+ u_long_int_write(size, file_out);
+ u_long_int_write(width, file_out);
+ long_int_write(height, file_out);
+ u_short_int_write(planes, file_out);
+ u_short_int_write(bitsperpixel, file_out);
+ u_long_int_write(compression, file_out);
+ u_long_int_write(sizeofbitmap, file_out);
+ u_long_int_write(horzresolution, file_out);
+ u_long_int_write(vertresolution, file_out);
+ u_long_int_write(colorsused, file_out);
+ u_long_int_write(colorsimportant, file_out);
+
+ return;
+}
+//****************************************************************************
+
+static bool bmp_palette_read(ifstream &file_in, unsigned long int colorsused,
+ unsigned char *rparray, unsigned char *gparray,
+ unsigned char *bparray, unsigned char *aparray)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_PALETTE_READ reads the palette information of a BMP file.
+//
+// Discussion:
+//
+// There are COLORSUSED colors listed. For each color, the values of
+// (B,G,R,A) are listed, where A is a quantity reserved for future use.
+//
+// Modified:
+//
+// 05 March 2003
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Input, unsigned long int COLORSUSED, the number of colors in the palette.
+//
+// Input, unsigned char *RPARRAY, *GPARRAY, *BPARRAY, *APARRAY pointers to
+// the red, green, blue and transparency palette arrays.
+//
+// Output, bool BMP_PALETTE_READ, is true if an error occurred.
+//
+{
+ char c;
+ bool error;
+ unsigned char *indexa;
+ unsigned char *indexb;
+ unsigned char *indexg;
+ unsigned char *indexr;
+
+ indexr = rparray;
+ indexg = gparray;
+ indexb = bparray;
+ indexa = aparray;
+
+ for (unsigned int i = 0; i < colorsused; i++) {
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_PALETTE_READ: Fatal error!\n";
+ cout << " Failed reading B for palette color " << i << ".\n";
+ return error;
+ }
+
+ *indexb = (unsigned char)c;
+ indexb = indexb + 1;
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_PALETTE_READ: Fatal error!\n";
+ cout << " Failed reading G for palette color " << i << ".\n";
+ return error;
+ }
+
+ *indexg = (unsigned char)c;
+ indexg = indexg + 1;
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_PALETTE_READ: Fatal error!\n";
+ cout << " Failed reading R for palette color " << i << ".\n";
+ return error;
+ }
+
+ *indexr = (unsigned char)c;
+ indexr = indexr + 1;
+
+ file_in.read(&c, 1);
+
+ error = file_in.eof();
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_PALETTE_READ: Fatal error!\n";
+ cout << " Failed reading A for palette color " << i << ".\n";
+ return error;
+ }
+
+ *indexa = (unsigned char)c;
+ indexa = indexa + 1;
+ }
+
+ error = false;
+ return error;
+}
+//****************************************************************************
+
+static void bmp_palette_write(ofstream &file_out, unsigned long int colorsused,
+ unsigned char *rparray, unsigned char *gparray,
+ unsigned char *bparray, unsigned char *aparray)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_PALETTE_WRITE writes the palette data to the BMP file.
+//
+// Modified:
+//
+// 04 March 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, ofstream &FILE_OUT, a reference to the output file.
+//
+// Input, unsigned long int COLORSUSED, the number of colors in the palette.
+//
+// Input, unsigned char *RPARRAY, *GPARRAY, *BPARRAY, *APARRAY, pointers to
+// the red, green, blue and transparency palette arrays.
+//
+{
+ unsigned char *indexa;
+ unsigned char *indexb;
+ unsigned char *indexg;
+ unsigned char *indexr;
+
+ indexr = rparray;
+ indexg = gparray;
+ indexb = bparray;
+ indexa = aparray;
+
+ for (unsigned int i = 0; i < colorsused; i++) {
+ file_out << *indexb;
+ file_out << *indexg;
+ file_out << *indexr;
+ file_out << *indexa;
+
+ indexb = indexb + 1;
+ indexg = indexg + 1;
+ indexr = indexr + 1;
+ indexa = indexa + 1;
+ }
+
+ return;
+}
+//****************************************************************************
+
+//****************************************************************************
+
+bool bmp_read(char *file_in_name, unsigned long int *width, long int *height,
+ unsigned char **rarray, unsigned char **garray,
+ unsigned char **barray)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_READ reads the header and data of a BMP file.
+//
+// Discussion:
+//
+// Thanks to Tak Fung for suggesting that BMP files should be opened with
+// the binary option.
+//
+// Thanks to Kelly Anderson for discovering that the routine could not read
+// monochrome images (bitsperpixel = 8 ) and suggesting how to fix that.
+//
+// Modified:
+//
+// 01 April 2005
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, char *FILE_IN_NAME, the name of the input file.
+//
+// Output, unsigned long int *WIDTH, the X dimension of the image.
+//
+// Output, long int *HEIGHT, the Y dimension of the image.
+//
+// Output, unsigned char **RARRAY, **GARRAY, **BARRAY, pointers to the red,
+// green and blue color arrays.
+//
+// Output, bool BMP_READ, is true if an error occurred.
+//
+{
+ unsigned char *aparray;
+ unsigned long int bitmapoffset;
+ unsigned short int bitsperpixel;
+ unsigned char *bparray;
+ unsigned long int colorsimportant;
+ unsigned long int colorsused;
+ unsigned long int compression;
+ bool error;
+ ifstream file_in;
+ unsigned long int filesize;
+ unsigned short int filetype;
+ unsigned char *gparray;
+ unsigned long int horzresolution;
+ unsigned short int magic;
+ int numbytes;
+ unsigned short int planes;
+ unsigned short int reserved1;
+ unsigned short int reserved2;
+ unsigned char *rparray;
+ unsigned long int size;
+ unsigned long int sizeofbitmap;
+ unsigned long int vertresolution;
+ //
+ // Open the input file.
+ //
+ file_in.open(file_in_name, ios::in | ios::binary);
+
+ if (!file_in) {
+ error = true;
+ cout << "\n";
+ cout << "BMP_READ - Fatal error!\n";
+ cout << " Could not open the input file.\n";
+ return error;
+ }
+ //
+ // Read header 1.
+ //
+ error = bmp_header1_read(file_in, &filetype, &filesize, &reserved1,
+ &reserved2, &bitmapoffset);
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_READ: Fatal error!\n";
+ cout << " BMP_HEADER1_READ failed.\n";
+ return error;
+ }
+ //
+ // Make sure the filetype is 'BM'.
+ //
+ magic = 'B' * 256 + 'M';
+
+ if (filetype != magic) {
+ cout << "\n";
+ cout << "BMP_READ: Fatal error!\n";
+ cout << " The file's internal magic number is not \"BM\".\n";
+ cout << " with the numeric value " << magic << "\n";
+ cout << "\n";
+ cout << " Instead, it is \"" << (char)(filetype / 256)
+ << (char)(filetype % 256) << "\".\n";
+ cout << " with the numeric value " << filetype << "\n";
+ cout << "\n";
+ cout << " (Perhaps you need to reverse the byte swapping option!)\n";
+ return 1;
+ }
+ //
+ // Read header 2.
+ //
+ error =
+ bmp_header2_read(file_in, &size, width, height, &planes, &bitsperpixel,
+ &compression, &sizeofbitmap, &horzresolution,
+ &vertresolution, &colorsused, &colorsimportant);
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_READ: Fatal error!\n";
+ cout << " BMP_HEADER2_READ failed.\n";
+ return error;
+ }
+ //
+ // Read the palette.
+ //
+ if (0 < colorsused) {
+ rparray = new unsigned char[colorsused];
+ gparray = new unsigned char[colorsused];
+ bparray = new unsigned char[colorsused];
+ aparray = new unsigned char[colorsused];
+
+ error = bmp_palette_read(file_in, colorsused, rparray, gparray, bparray,
+ aparray);
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_READ: Fatal error!\n";
+ cout << " BMP_PALETTE_READ failed.\n";
+ return error;
+ }
+ delete[] rparray;
+ delete[] gparray;
+ delete[] bparray;
+ delete[] aparray;
+ }
+ //
+ // Allocate storage.
+ //
+ numbytes = (*width) * (abs(*height)) * sizeof(unsigned char);
+
+ *rarray = new unsigned char[numbytes];
+ *garray = new unsigned char[numbytes];
+ *barray = new unsigned char[numbytes];
+ //
+ // Read the data.
+ //
+ if (bitsperpixel == 8) {
+ error = bmp_08_data_read(file_in, *width, *height, *rarray);
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_READ: Fatal error!\n";
+ cout << " BMP_08_DATA_READ failed.\n";
+ return error;
+ }
+
+ *garray = *rarray;
+ *barray = *rarray;
+ } else if (bitsperpixel == 24) {
+ error =
+ bmp_24_data_read(file_in, *width, *height, *rarray, *garray, *barray);
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_READ: Fatal error!\n";
+ cout << " BMP_24_DATA_READ failed.\n";
+ return error;
+ }
+ } else {
+ cout << "\n";
+ cout << "BMP_READ: Fatal error!\n";
+ cout << " Unrecognized value of BITSPERPIXEL = " << bitsperpixel << "\n";
+ return 1;
+ }
+ //
+ // Close the file.
+ //
+ file_in.close();
+
+ error = false;
+ return error;
+}
+
+//****************************************************************************
+
+static bool bmp_24_write(char *file_out_name, unsigned long int width,
+ long int height, unsigned char *rarray,
+ unsigned char *garray, unsigned char *barray)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// BMP_24_WRITE writes the header and data for a BMP file using three colors.
+//
+// Discussion
+//
+// Thanks to Keefe Roedersheimer for pointing out that I was creating
+// a filetype of 'MB' instead of 'BM'.
+//
+// Lee Mulcahy pointed out that the BMP format requires that horizonal lines
+// must have a length that is a multiple of 4, or be padded so that this is
+// the case.
+//
+// Thanks to Tak Fung for suggesting that BMP files should be opened with
+// the binary option.
+//
+// Modified:
+//
+// 02 April 2005
+//
+// Author:
+//
+// John Burkardt
+//
+// References:
+//
+// David Kay and John Levine,
+// Graphics File Formats,
+// Second Edition,
+// McGraw Hill, 1995.
+//
+// Microsoft Corporation,
+// Microsoft Windows Programmer's Reference,
+// Volume 5; Messages, Structures, and Macros,
+// Microsoft Press, 1993.
+//
+// John Miano,
+// Compressed Image File Formats,
+// Addison Wesley, 1999.
+//
+// Parameters:
+//
+// Input, char *FILE_OUT_NAME, the name of the output file.
+//
+// Input, unsigned long int WIDTH, the X dimension of the image.
+//
+// Input, long int HEIGHT, the Y dimension of the image.
+//
+// Input, unsigned char *RARRAY, *GARRAY, *BARRAY, pointers to the red, green
+// and blue color arrays.
+//
+// Output, bool BMP_24_WRITE, is true if an error occurred.
+//
+{
+ unsigned char *aparray = NULL;
+ unsigned long int bitmapoffset;
+ unsigned short int bitsperpixel;
+ unsigned char *bparray = NULL;
+ unsigned long int colorsimportant;
+ unsigned long int colorsused;
+ unsigned long int compression;
+ bool error;
+ ofstream file_out;
+ unsigned long int filesize;
+ unsigned short int filetype;
+ unsigned char *gparray = NULL;
+ unsigned long int horzresolution;
+ int padding;
+ unsigned short int planes;
+ unsigned short int reserved1 = 0;
+ unsigned short int reserved2 = 0;
+ unsigned char *rparray = NULL;
+ unsigned long int size = 40;
+ unsigned long int sizeofbitmap;
+ unsigned long int vertresolution;
+ //
+ // Open the output file.
+ //
+ file_out.open(file_out_name, ios::out | ios::binary);
+
+ error = !file_out;
+
+ if (error) {
+ cout << "\n";
+ cout << "BMP_24_WRITE - Fatal error!\n";
+ cout << " Could not open the output file.\n";
+ return error;
+ }
+ //
+ // Write header 1.
+ //
+ if (bmp_byte_swap) {
+ filetype = 'M' * 256 + 'B';
+ } else {
+ filetype = 'B' * 256 + 'M';
+ }
+ //
+ // Determine the padding needed when WIDTH is not a multiple of 4.
+ //
+ padding = (4 - ((3 * width) % 4)) % 4;
+
+ filesize = 54 + ((3 * width) + padding) * abs(height);
+ bitmapoffset = 54;
+
+ bmp_header1_write(file_out, filetype, filesize, reserved1, reserved2,
+ bitmapoffset);
+ //
+ // Write header 2.
+ //
+ planes = 1;
+ bitsperpixel = 24;
+ compression = 0;
+ sizeofbitmap = 0;
+ horzresolution = 0;
+ vertresolution = 0;
+ colorsused = 0;
+ colorsimportant = 0;
+
+ bmp_header2_write(file_out, size, width, height, planes, bitsperpixel,
+ compression, sizeofbitmap, horzresolution, vertresolution,
+ colorsused, colorsimportant);
+ //
+ // Write the palette.
+ //
+ bmp_palette_write(file_out, colorsused, rparray, gparray, bparray, aparray);
+ //
+ // Write the data.
+ //
+ bmp_24_data_write(file_out, width, height, rarray, garray, barray);
+ //
+ // Close the file.
+ //
+ file_out.close();
+
+ error = false;
+ return error;
+}
+
+//****************************************************************************
+
+static bool long_int_read(long int *long_int_val, ifstream &file_in)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// LONG_INT_READ reads a long int from a file.
+//
+// Modified:
+//
+// 06 March 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// Parameters:
+//
+// Output, long int *LONG_INT_VAL, the value that was read.
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Output, bool LONG_INT_READ, is true if an error occurred.
+//
+{
+ bool error;
+ unsigned short int u_short_int_val_hi;
+ unsigned short int u_short_int_val_lo;
+
+ if (bmp_byte_swap) {
+ error = u_short_int_read(&u_short_int_val_lo, file_in);
+ if (error) {
+ return error;
+ }
+ error = u_short_int_read(&u_short_int_val_hi, file_in);
+ if (error) {
+ return error;
+ }
+ } else {
+ error = u_short_int_read(&u_short_int_val_hi, file_in);
+ if (error) {
+ return error;
+ }
+ error = u_short_int_read(&u_short_int_val_lo, file_in);
+ if (error) {
+ return error;
+ }
+ }
+
+ *long_int_val = (long int)(u_short_int_val_hi << 16) | u_short_int_val_lo;
+
+ return false;
+}
+//****************************************************************************
+
+static void long_int_write(long int long_int_val, ofstream &file_out)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// LONG_INT_WRITE writes a long int to a file.
+//
+// Modified:
+//
+// 06 March 2004
+//
+// Author:
+//
+// John Burkardt
+//
+// Parameters:
+//
+// Input, long int *LONG_INT_VAL, the value to be written.
+//
+// Input, ofstream &FILE_OUT, a reference to the output file.
+//
+{
+ long int temp;
+ unsigned short int u_short_int_val_hi;
+ unsigned short int u_short_int_val_lo;
+
+ temp = long_int_val / 65536;
+ if (temp < 0) {
+ temp = temp + 65536;
+ }
+ u_short_int_val_hi = (unsigned short)temp;
+
+ temp = long_int_val % 65536;
+ if (temp < 0) {
+ temp = temp + 65536;
+ }
+ u_short_int_val_lo = (unsigned short)temp;
+
+ if (bmp_byte_swap) {
+ u_short_int_write(u_short_int_val_lo, file_out);
+ u_short_int_write(u_short_int_val_hi, file_out);
+ } else {
+ u_short_int_write(u_short_int_val_hi, file_out);
+ u_short_int_write(u_short_int_val_lo, file_out);
+ }
+
+ return;
+}
+//****************************************************************************
+
+static bool u_long_int_read(unsigned long int *u_long_int_val,
+ ifstream &file_in)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// U_LONG_INT_READ reads an unsigned long int from a file.
+//
+// Modified:
+//
+// 05 March 2003
+//
+// Author:
+//
+// John Burkardt
+//
+// Parameters:
+//
+// Output, unsigned long int *U_LONG_INT_VAL, the value that was read.
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Output, bool U_LONG_INT_READ, is true if an error occurred.
+//
+{
+ bool error;
+ unsigned short int u_short_int_val_hi;
+ unsigned short int u_short_int_val_lo;
+
+ if (bmp_byte_swap) {
+ error = u_short_int_read(&u_short_int_val_lo, file_in);
+ if (error) {
+ return error;
+ }
+ error = u_short_int_read(&u_short_int_val_hi, file_in);
+ if (error) {
+ return error;
+ }
+ } else {
+ error = u_short_int_read(&u_short_int_val_hi, file_in);
+ if (error) {
+ return error;
+ }
+ error = u_short_int_read(&u_short_int_val_lo, file_in);
+ if (error) {
+ return error;
+ }
+ }
+ //
+ // Acknowledgement:
+ //
+ // A correction to the following line was supplied by
+ // Peter Kionga-Kamau, 20 May 2000.
+ //
+
+ *u_long_int_val = (u_short_int_val_hi << 16) | u_short_int_val_lo;
+
+ return false;
+}
+//****************************************************************************
+
+static void u_long_int_write(unsigned long int u_long_int_val,
+ ofstream &file_out)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// U_LONG_INT_WRITE writes an unsigned long int to a file.
+//
+// Modified:
+//
+// 05 March 2003
+//
+// Author:
+//
+// John Burkardt
+//
+// Parameters:
+//
+// Input, unsigned long int *U_LONG_INT_VAL, the value to be written.
+//
+// Input, ofstream &FILE_OUT, a reference to the output file.
+//
+{
+ unsigned short int u_short_int_val_hi;
+ unsigned short int u_short_int_val_lo;
+
+ u_short_int_val_hi = (unsigned short)(u_long_int_val / 65536);
+ u_short_int_val_lo = (unsigned short)(u_long_int_val % 65536);
+
+ if (bmp_byte_swap) {
+ u_short_int_write(u_short_int_val_lo, file_out);
+ u_short_int_write(u_short_int_val_hi, file_out);
+ } else {
+ u_short_int_write(u_short_int_val_hi, file_out);
+ u_short_int_write(u_short_int_val_lo, file_out);
+ }
+
+ return;
+}
+//****************************************************************************
+
+static bool u_short_int_read(unsigned short int *u_short_int_val,
+ ifstream &file_in)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// U_SHORT_INT_READ reads an unsigned short int from a file.
+//
+// Modified:
+//
+// 30 March 2005
+//
+// Author:
+//
+// John Burkardt
+//
+// Parameters:
+//
+// Output, unsigned short int *U_SHORT_INT_VAL, the value that was read.
+//
+// Input, ifstream &FILE_IN, a reference to the input file.
+//
+// Output, bool U_SHORT_INT_READ, is true if an error occurred.
+//
+{
+ char c;
+ unsigned char chi;
+ unsigned char clo;
+
+ if (bmp_byte_swap) {
+ file_in.read(&c, 1);
+ if (file_in.eof()) {
+ return true;
+ }
+ clo = (unsigned char)c;
+
+ file_in.read(&c, 1);
+ if (file_in.eof()) {
+ return true;
+ }
+ chi = (unsigned char)c;
+ } else {
+ file_in.read(&c, 1);
+ if (file_in.eof()) {
+ return true;
+ }
+ chi = (unsigned char)c;
+
+ file_in.read(&c, 1);
+ if (file_in.eof()) {
+ return true;
+ }
+ clo = (unsigned char)c;
+ }
+
+ *u_short_int_val = (chi << 8) | clo;
+
+ return false;
+}
+//****************************************************************************
+
+static void u_short_int_write(unsigned short int u_short_int_val,
+ ofstream &file_out)
+
+//****************************************************************************
+//
+// Purpose:
+//
+// U_SHORT_INT_WRITE writes an unsigned short int to a file.
+//
+// Modified:
+//
+// 26 February 2003
+//
+// Author:
+//
+// John Burkardt
+//
+// Parameters:
+//
+// Input, unsigned short int *U_SHORT_INT_VAL, the value to be written.
+//
+// Input, ofstream &FILE_OUT, a reference to the output file.
+//
+{
+ unsigned char chi;
+ unsigned char clo;
+
+ chi = (unsigned char)(u_short_int_val / 256);
+ clo = (unsigned char)(u_short_int_val % 256);
+
+ if (bmp_byte_swap) {
+ file_out << clo << chi;
+ } else {
+ file_out << chi << clo;
+ }
+
+ return;
+}
+
+/////////////////////////////////////////////////////////////////////////////
+//
+// CS1300 interface routines
+//
+/////////////////////////////////////////////////////////////////////////////
+
+int cs1300bmp_readfile(char *filename, struct cs1300bmp *image) {
+ bool error;
+ unsigned char *rarray;
+ unsigned char *garray;
+ unsigned char *barray;
+
+ long int height;
+ unsigned long int width;
+
+ rarray = NULL;
+ garray = NULL;
+ barray = NULL;
+ //
+ // Read the data from file.
+ //
+ error = bmp_read(filename, &width, &height, &rarray, &garray, &barray);
+ if (error) {
+ //
+ // Free the memory.
+ //
+ delete[] rarray;
+ delete[] garray;
+ delete[] barray;
+ return 0;
+ } else {
+ //
+ // Copy the image from the flat representation to the array used for cs1300
+ //
+ image->width = width;
+ image->height = height;
+ for (int row = 0; row < height; row++) {
+ for (unsigned int col = 0; col < width; col++) {
+ image->color[COLOR_RED][row][col] = rarray[row * width + col];
+ image->color[COLOR_GREEN][row][col] = garray[row * width + col];
+ image->color[COLOR_BLUE][row][col] = barray[row * width + col];
+ }
+ }
+ //
+ // Free the memory.
+ //
+ delete[] rarray;
+ delete[] garray;
+ delete[] barray;
+
+ //
+ // Success
+ //
+ return (1);
+ }
+}
+
+int cs1300bmp_writefile(char *filename, struct cs1300bmp *image) {
+ int colorbytes = image->width * image->height;
+
+ unsigned char *rarray = new unsigned char[colorbytes];
+ unsigned char *garray = new unsigned char[colorbytes];
+ unsigned char *barray = new unsigned char[colorbytes];
+
+ int height = image->height;
+ int width = image->width;
+ for (int row = 0; row < height; row++) {
+ for (int col = 0; col < width; col++) {
+ rarray[row * width + col] = image->color[COLOR_RED][row][col];
+ garray[row * width + col] = image->color[COLOR_GREEN][row][col];
+ barray[row * width + col] = image->color[COLOR_BLUE][row][col];
+ }
+ }
+
+ int error = bmp_24_write(filename, image->width, image->height, rarray,
+ garray, barray);
+
+ delete[] rarray;
+ delete[] garray;
+ delete[] barray;
+
+ if (error) {
+ return 0;
+ } else {
+ return 1;
+ }
+}
diff --git a/lab4_perflab/cs1300bmp.h b/lab4_perflab/cs1300bmp.h
new file mode 100644
index 0000000..6fcc09d
--- /dev/null
+++ b/lab4_perflab/cs1300bmp.h
@@ -0,0 +1,48 @@
+//-*-c++-*-
+#ifndef _cs1300bmp_h_
+#define _cs1300bmp_h_
+
+//
+// Maximum image size
+//
+#define MAX_DIM 1024
+
+//
+// The specific colors
+//
+#define COLOR_RED 0
+#define COLOR_GREEN 1
+#define COLOR_BLUE 2
+#define MAX_COLORS 3
+
+struct cs1300bmp {
+ //
+ // Actual width used by this image
+ //
+ int width;
+ //
+ // Actual height used by this image
+ //
+ int height;
+ //
+ // R/G/B fields
+ //
+ int color[MAX_COLORS][MAX_DIM][MAX_DIM];
+};
+
+//
+// routines to read and write BMP images
+//
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+int cs1300bmp_readfile(char *filename, struct cs1300bmp *image);
+int cs1300bmp_writefile(char *filename, struct cs1300bmp *image);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
diff --git a/lab4_perflab/edge.filter b/lab4_perflab/edge.filter
new file mode 100644
index 0000000..4d515e9
--- /dev/null
+++ b/lab4_perflab/edge.filter
@@ -0,0 +1,5 @@
+3
+1
+1 1 1
+1 -7 1
+1 1 1
diff --git a/lab4_perflab/emboss.filter b/lab4_perflab/emboss.filter
new file mode 100644
index 0000000..93ac197
--- /dev/null
+++ b/lab4_perflab/emboss.filter
@@ -0,0 +1,5 @@
+3
+1
+1 1 -1
+1 1 -1
+1 -1 -1
diff --git a/lab4_perflab/gauss.filter b/lab4_perflab/gauss.filter
new file mode 100644
index 0000000..09827d7
--- /dev/null
+++ b/lab4_perflab/gauss.filter
@@ -0,0 +1,5 @@
+3
+24
+0 4 0
+4 8 4
+0 4 0
diff --git a/lab4_perflab/hline.filter b/lab4_perflab/hline.filter
new file mode 100644
index 0000000..ec9c5e2
--- /dev/null
+++ b/lab4_perflab/hline.filter
@@ -0,0 +1,5 @@
+3
+1
+-1 -2 -1
+0 0 0
+1 2 1
diff --git a/lab4_perflab/optimisation.md b/lab4_perflab/optimisation.md
new file mode 100644
index 0000000..24f2907
--- /dev/null
+++ b/lab4_perflab/optimisation.md
@@ -0,0 +1,83 @@
+### optimisations
+first and foremost, GCC can perform various optimisations with `-O*` flag. `O3` and `Ofast` perform comparatively on this program,
+however `Ofast` applies some optimisations that are considered unsafe in some instances.
+
+in the `applyFilter()` function, there's a loop that calls `getSize()` on every iteration, while the value does not change. so we can
+make the following change:
+```diff
+ output->width = input->width;
+ output->height = input->height;
++ int filter_size = filter->getSize();
++
+ for (int col = 1; col < (input->width) - 1; col = col + 1) {
+ for (int row = 1; row < (input->height) - 1; row = row + 1) {
+ for (int plane = 0; plane < 3; plane++) {
+
+ output->color[plane][row][col] = 0;
+
+- for (int j = 0; j < filter->getSize(); j++) {
+- for (int i = 0; i < filter->getSize(); i++) {
++ for (int j = 0; j < filter_size; j++) {
++ for (int i = 0; i < filter_size; i++) {
+ output->color[plane][row][col] =
+```
+
+in the same loop, we can reduce memory references when accessing class variables:
+```diff
+ cycStart = rdtscll();
+
++ int input_width = input->width;
++ int input_height = input->height;
+
+- output->width = input->width;
+- output->height = input->height;
++ output->width = input_width;
++ output->height = input_height;
+
+- for (int col = 1; col < (input->width) - 1; col = col + 1) {
+- for (int row = 1; row < (input->height) - 1; row = row + 1) {
++ for (int col = 1; col < input_width - 1; col = col + 1) {
++ for (int row = 1; row < input_height - 1; row = row + 1) {
+ for (int plane = 0; plane < 3; plane++) {
+ output->color[plane][row][col] = 0;
+```
+
+the 3 dimensional array `color` is traversed in column-major order:
+```
+x[0 0] x[0 1] x[0 2]
+ ↓ ↓ ↓
+x[1 0] x[1 1] x[1 2]
+ ↓ ↓ ↓
+x[2 0] x[2 1] x[2 2]
+```
+
+accessing sequential data using SIMD methods is much more efficient (row-major order):
+```
+x[0 0] → x[0 1] → x[0 2]
+x[1 0] → x[1 1] → x[1 2]
+x[2 0] → x[2 1] → x[2 2]
+```
+
+so we can reorder how the array is processed:
+```diff
+ output->height = input_height;
+
+- for (int col = 1; col < input_width - 1; col = col + 1) {
++ for (int plane = 0; plane < 3; plane++) {
+ for (int row = 1; row < input_height - 1; row = row + 1) {
+- for (int plane = 0; plane < 3; plane++) {
++ for (int col = 1; col < input_width - 1; col = col + 1) {
+
+ output->color[plane][row][col] = 0;
+```
+
+next, i simply removed this line to make the loops stack up nicely and it somehow
+did not cause any errors and improved performance???
+```diff
+ for (int plane = 0; plane < 3; plane++) {
+ for (int row = 1; row < input_height - 1; row = row + 1) {
+ for (int col = 1; col < input_width - 1; col = col + 1) {
+- output->color[plane][row][col] = 0;
+ for (int j = 0; j < filter_size; j++) {
+ for (int i = 0; i < filter_size; i++) {
+```
diff --git a/lab4_perflab/rdtsc.h b/lab4_perflab/rdtsc.h
new file mode 100644
index 0000000..ecfa739
--- /dev/null
+++ b/lab4_perflab/rdtsc.h
@@ -0,0 +1,17 @@
+//-*-c++-*-
+#ifndef _rtdsc_h_
+#define _rtdsc_h_
+
+//
+// Inline function to read the CPU clock
+//
+inline unsigned long long int rdtscll(void) {
+ unsigned a, d;
+
+ __asm__ volatile("rdtsc" : "=a"(a), "=d"(d));
+
+ return ((unsigned long long)a) | (((unsigned long long)d) << 32);
+ ;
+}
+
+#endif
diff --git a/lab4_perflab/sharpen.filter b/lab4_perflab/sharpen.filter
new file mode 100644
index 0000000..5b26b65
--- /dev/null
+++ b/lab4_perflab/sharpen.filter
@@ -0,0 +1,5 @@
+3
+20
+11 10 1
+-1 -1 -1
+-1 -1 -1
diff --git a/lab4_perflab/tests/filtered-avg-blocks-small.bmp b/lab4_perflab/tests/filtered-avg-blocks-small.bmp
new file mode 100644
index 0000000..106df6d
--- /dev/null
+++ b/lab4_perflab/tests/filtered-avg-blocks-small.bmp
Binary files differ
diff --git a/lab4_perflab/tests/filtered-avg-boats.bmp b/lab4_perflab/tests/filtered-avg-boats.bmp
new file mode 100644
index 0000000..7d333e7
--- /dev/null
+++ b/lab4_perflab/tests/filtered-avg-boats.bmp
Binary files differ
diff --git a/lab4_perflab/tests/filtered-emboss-blocks-small.bmp b/lab4_perflab/tests/filtered-emboss-blocks-small.bmp
new file mode 100644
index 0000000..3a465bc
--- /dev/null
+++ b/lab4_perflab/tests/filtered-emboss-blocks-small.bmp
Binary files differ
diff --git a/lab4_perflab/tests/filtered-emboss-boats.bmp b/lab4_perflab/tests/filtered-emboss-boats.bmp
new file mode 100644
index 0000000..7434c2e
--- /dev/null
+++ b/lab4_perflab/tests/filtered-emboss-boats.bmp
Binary files differ
diff --git a/lab4_perflab/tests/filtered-gauss-blocks-small.bmp b/lab4_perflab/tests/filtered-gauss-blocks-small.bmp
new file mode 100644
index 0000000..728d369
--- /dev/null
+++ b/lab4_perflab/tests/filtered-gauss-blocks-small.bmp
Binary files differ
diff --git a/lab4_perflab/tests/filtered-gauss-boats.bmp b/lab4_perflab/tests/filtered-gauss-boats.bmp
new file mode 100644
index 0000000..c38dacb
--- /dev/null
+++ b/lab4_perflab/tests/filtered-gauss-boats.bmp
Binary files differ
diff --git a/lab4_perflab/tests/filtered-hline-blocks-small.bmp b/lab4_perflab/tests/filtered-hline-blocks-small.bmp
new file mode 100644
index 0000000..b475a7c
--- /dev/null
+++ b/lab4_perflab/tests/filtered-hline-blocks-small.bmp
Binary files differ
diff --git a/lab4_perflab/tests/filtered-hline-boats.bmp b/lab4_perflab/tests/filtered-hline-boats.bmp
new file mode 100644
index 0000000..4d14c40
--- /dev/null
+++ b/lab4_perflab/tests/filtered-hline-boats.bmp
Binary files differ
diff --git a/lab4_perflab/vline.filter b/lab4_perflab/vline.filter
new file mode 100644
index 0000000..bd995bb
--- /dev/null
+++ b/lab4_perflab/vline.filter
@@ -0,0 +1,5 @@
+3
+1
+-1 0 1
+-2 0 2
+-1 0 1