gcc link-time optimization

Link optimization can give impressive results (at least regarding executable size as presented below).
Here is output from simple program build. The program consists of 3 modules and 2 header files (6 functions in total).

• Normal compilation (and linking), no optimization 'gcc mod1.c mod2.c mod3.c -o test'
  stripped executable size - 14480.
• Normal compilation (and linking), optimized for size 'gcc mod1.c mod2.c mod3.c -o test -Os'
  stripped executable size - 10384.
• LTO compilation (and linking), no optimization 'gcc mod1.c mod2.c mod3.c -o test -flto'
  stripped executable size - 10384.
• LTO compilation (and linking), optimized for size 'gcc mod1.c mod2.c mod3.c -o test -flto -Os'
  stripped executable size - 6288.

GCC version used 4.8.2 (x86-64).

Please note that compilation time and output code speed was not taken into account in simple example consideration above.
Also for sure example is far too simple to treat it as meaningful case, please treat it just as remark of LTO possibilities.

References

1. gcc.gnu.org/onlinedocs/gcc/Optimize-Options.html#index-flto-934
2. gcc.gnu.org/wiki/summit2010?action=AttachFile&do=get&target=hubicka.pdf
3. en.wikipedia.org/wiki/Link-time_optimization

How to skip every n-th byte in binary file from Linux command

Here is solution to do it from shell using 'xxd' and 'sed'.
E.g. to copy every 4th byte from binary in_file to out_file:

xxd -p -c4 in_file | sed 's/\(.\{6\}\)\(..\)/\2/g' | xxd -p -r >out_file

ADS1278EVM-PDK in Linux

Please take into account that I do not take any responsibility for any damage caused through use of presented solution.

As TI does not support Linux for its evaluation module here is presented simple solution to trigger data acquisition from Linux command line.

First step in order to run under Linux firmware has to be loaded into MMB0 board.
Firmware exists in "ads1278.bin" file somewhere in "ProgramFiles\ADSPro\...".
According to documentation parameters necessary to communicate with MMB0 via USB are following:
VENDOR_ID = 0x0451
PRODUCT_ID = 0x9001
ENDPOINT_ADDR = 0x06
Endpoint is bulk type waiting for data from PC.
Here is simple app to load firmware from userspace.
Application uses libusb-1.0 library therefore can be build with e.g.:

g++ -I /usr/include/libusb-1.0/ -l usb-1.0 usbfirmwareload.cpp -o usbfirmwareload


To load firmware just run "usbfirmwareload" from folder where "ads1278.bin" is stored (to do that perhaps you should be root).

After firmware is successfully uploaded led segment shall show letter "S" (BTW it looks quite strange).

Next step is to perform communication with loaded software.
First thing to spot is change in USB configuration, now we have:
VENDOR_ID = 0x0451
PRODUCT_ID = 0x5718

and two endpoints have appeared - for both data directions:

0x01 - output endpoint,

0x81 - input endpoint.

Communication protocol is build upon "cstyx" library which provides bunch of function that realizes communication as virtual filesystem. Library can be downloaded using SVN:

svn checkout svn://svn.berlios.de/cstyx

In following location archive with minimal version of the library necessary for communication is prepared. It also contains simple and dirty makefile to build the library.

With prepared library it is possible to send requests to MMB0 and receive data. Application to perform arbitrary operation in cstyx virtual filesystem is also available in archive file - please use makefile from "app" folder (after library is built in "cstyxminlib" folder).
Note that cstyx uses libusb and not libusb-1.0 library for USB communication therefore libusb is also required to be available in system.

With "adscomm" application it is easy to invoke operations on MMB0, e.g. to change digit in led segment to "8" following command can be used:

./adscomm -p "/mmb0/led/ch" -w 8

allowed params are:

• -p XXX - use path XXX in cstyx virtual filessytem,
• -w YYY- write YYY to file XXX specified with -p,
• -r - read from file XXX specified with -p,
• -f ZZZ - read from file XXX specified with -p and stored values in file ZZZ.

Command can be chained to perform multiple actions one after another, e.g.:

./adscomm -p "/version" -r -p "/mmb0/led/ch" -w 1

prints version read from MMB0 and changes led digit to 1.

In "app" directory simple scripts are available:

• initcomm - performs default initialization (tries to mimic ADCPro initialization for ADS1278EVM),
• inithighres - initializes ADS1278EVM for high-resolution acquisiton,
• record - reads 10000 samples from all channels and stores data in "data" file (in current directory).

After measurement is finished it would be nice to see the values - it can be done with last file "plotdata".

The file contains description to parse binary file content for gnuplot application.

After following command invoked:

gnuplot -p plotdata

one can see the results:

Camera orientation v.s. Orientation EXIF tag in Canon pictures

There is problem with pictures orientation I have found for my old 450D.
Exif tag shows always e.g.:

exiftool -H -G:0:1 -Orientation IMG_6071.JPG
[EXIF:IFD0]     0x0112 Orientation                     : Horizontal (normal)


even when camera was rotated.Then all default programs for pictures presentation are unable to recognize proper orientation (picture is rotated).
The reason is additional tag (Canon specific) e.g.:

exiftool -H -G:0:1 -*Orientation IMG_6071.JPG
[EXIF:IFD0]     0x0112 Orientation                     : Horizontal (normal)
[MakerNotes:Canon] 0x0030 Camera Orientation           : Rotate 270 CW


and in numerical form:

exiftool -H -G:0:1 -*Orientation# IMG_6071.JPG
[EXIF:IFD0]     0x0112 Orientation                     : 1
[MakerNotes:Canon] 0x0030 Camera Orientation           : 2


Therefore what is needed is mapping to move orientation from camera to EXIF Orientation tag.

For example when "Camera Orientation" is 2 (Rotate 270CW) then "Orientation" should be 8 (also Rotate 270CW):

exiftool -Orientation#=8 IMG_6071.JPG

After changing "Orientation" it is necessary to reset "Camera Orientation" to 0 (Horizontal (normal)).

exiftool -CameraOrientation#=0 IMG_6071.JPG

Allowed values for Canon's "Camera Orientation":

• 0 - Horizontal (normal)
• 1 - Rotate 90 CW
• 2 - Rotate 270 CW

seems there is no more values defined for "Camera Orientation".

Unfortunately I was unable to find specification for Canon's specific tags.

These should be mapped onto standard EXIF "Orientation":

• 1 - Horizontal (normal)
• 6 - Rotate 90 CW
• 8 - Rotate 270 CW

Here is simple bash script (sure it can be sorter) which moves rotation form Camera to EXIF tag. It changes file only when original EXIF Orienation is normal and "Camera Orientation" is 90 or 270 (of course image data are not changed, only metadata).

#!/bin/bash

orientation=$(exiftool -p '${Orientation#} ${CameraOrientation#}' "$1")

orient_array=($orientation)

if [ ${orient_array[0]} -eq 1 ] ; then

    if [ ${orient_array[1]} -eq 1 ] ; then

echo "$1 - Camera Orientation - Rotate 90 CW - will be moved to EXIF Orientation";

# also reset Camera Orientation

exiftool -Orientation#=6 -CameraOrientation#=0 -overwrite_original $1

    elif [ ${orient_array[1]} -eq 2 ] ; then

echo "$1 - Camera Orientation - Rotate 270 CW - will be moved to EXIF Orientation";

# also reset Camera Orientation

exiftool -Orientation#=8 -CameraOrientation#=0 -overwrite_original $1

    fi

fi

Then to apply resize with ImageMagic "-auto-orient" option can be used e.g.:

convert -auto-orient -strip -resize x1080 file.jpg file_resized.jpg


GWT runtime NoSuchMethodError for sun.reflect.Reflection.getCallerClass

Problem in Java update breaks GWT - info here:
https://bugzilla.redhat.com/show_bug.cgi?id=976693

At the moment of writing this entry no stable update of java-1.7.0-openjdk exists.
But testing version (java-1.7.0-openjdk-1.7.0.25-2.3.10.5.fc17) is available and seems to work properly.
Use this for update:
sudo yum update --enablerepo=updates-testing java-1.7.0-openjdk

Why C++ is scary

Here is example why C++ is scary :)

  vector<signed char> vc;
  vc.push_back(1);
  vc.push_back(255);
  vc.push_back(1);
  vc.push_back(1);
  cout << find(vc.begin(), vc.end(), 255) - vc.begin() << endl;

More on K-D trees

Previous post shows how to properly and efficiently find closest point using k-d tree algorithm for latitude-logitude coordinates. Here is supplement to the topic. Additional features are:

• finding not one, but arbitrary number of closest points,
• finding all points within specified range from given location,
• make code easy to use for metrics different than lat-lng.

To find arbitrary number of points, what we need to store is not one but list of closest points. Additionally what we need to know is distance to the most distant point - to know whether newly checked shall replace the worst of stored. To achieve this property list of point has to be sorted according to distance from the source point. Below is listing of the method.

private void findNearest(PointNode<P> root, P point, int depth, LimitedSortedArrayList<D> results) {
D distance = point.getDistance(root.point);
if (root.left == null && root.right == null) {
results.addSorted(distance);
return;
}

final int axis = depth % 2;
boolean left = false;

if ((root.left != null) && (point.compareAxisTo(axis, root.point) < 0)) {
findNearest(root.left, point, depth+1, results);
left = true;
}
else if (root.right != null) {
findNearest(root.right, point, depth+1, results);
}

results.addSorted(distance);

if (!results.isFilled() || results.getWorst().compareAxisTo(axis, distance) >= 0) {
if (left) {
if (root.right != null) {
findNearest(root.right, point, depth+1, results);
}
}
else {
if (root.left != null) {
findNearest(root.left, point, depth+1, results);
}
}
}
}

Key point for algorithm above is "addSorted" method. This method is convenient extension of ArrayList implemented in LimitedSortedArrayList class, that allow only for limited storage of sorted items:

private static class LimitedSortedArrayList<T extends Comparable<T>> extends SortedArrayList<T> {
private int limit;

public LimitedSortedArrayList(int max_number) {
limit = max_number;
}
   public void addSorted(T value) {
      if (size() < limit) {
         insertSorted(value);
      }
      else {
        overwriteSorted(value);
      }
   }
   public boolean isFilled() {
      return size() >= limit;
   }
}

LimitedSortedArrayList extends ArrayList, but not directly only via SortedArrayList class. Responsibility of SortedArrayList is to keep order according to "compareTo", allow insertion of new elements and overwriting existing (to keep constant size of the container).

private static class SortedArrayList<T extends Comparable<T>> extends ArrayList<T> {
   private void sort() {
      for (int i = size()-1; i > 0 && get(i).compareTo(get(i-1)) < 0; i--)
        Collections.swap(this, i, i-1);
   }
   public T getWorst() {
      if (size() > 0) {
        return get(size()-1);
     }
      return null;
   }
   public void overwriteSorted(T value) {
      if (value.compareTo(getWorst()) < 0) {
        set(size()-1, value);
        sort();
      }
   }
   public void insertSorted(T value) {
add(value);
sort();
   }
}

Methods presented above do not contains exact types of point and means of distance calculation. These are provided via template parameters. P stands for point which must extend Metric interface and D stands for Distance and extends Distance interface.

public interface Metric<P, D extends Distance<D, P>> extends ComparableAxis<P> {
D getDistance(P other);
}
public interface Distance<D, P> extends Comparable<D>, ComparableAxis<D> {
P getToPoint();
}

where ComparableAxis is interface that allows for comparisons along specified axis:

public interface ComparableAxis<T> {
int compareAxisTo(int axis, T o);
}

For latitude-longitude we have following implementations of the interfaces:

public class LatLngCommon implements Metric<LatLngCommon, CosDistance> {
public double lat;
public double lng;
public double sin_lat;
public double cos_lat;
public double sin_lng;
public double cos_lng;

public LatLngCommon(double latitude, double longitude) {
lat = latitude;
lng = longitude;
double lat_rad = Math.toRadians(lat);
double lng_rad = Math.toRadians(lng);
sin_lat = Math.sin(lat_rad);
cos_lat = Math.cos(lat_rad);
sin_lng = Math.sin(lng_rad);
cos_lng = Math.cos(lng_rad);
}

@Override
public int compareAxisTo(int axis, LatLngCommon o) {
return (0==axis)
?(Double.compare(lat, o.lat))
:(Double.compare(lng, o.lng));
}
@Override
public CosDistance getDistance(LatLngCommon other) {
return new CosDistance(this, other);
}
}


public class CosDistance implements Distance<CosDistance, LatLngCommon> {

private LatLngCommon to_point;
private double sin_from_lat__sin_to_lat;
private double cos_from_lat__cos_to_lat;
private double sin_from_lng__sin_to_lng__cos_from_lng__cos_to_lng;
private double cos_dist;
private static final double RADIUS = 6371000.0;

public CosDistance(LatLngCommon from, LatLngCommon to) {
to_point = to;
sin_from_lat__sin_to_lat = from.sin_lat*to.sin_lat;
cos_from_lat__cos_to_lat = from.cos_lat*to.cos_lat;
sin_from_lng__sin_to_lng__cos_from_lng__cos_to_lng = from.sin_lng*to.sin_lng + from.cos_lng*to.cos_lng;
cos_dist = sin_from_lat__sin_to_lat + cos_from_lat__cos_to_lat*(sin_from_lng__sin_to_lng__cos_from_lng__cos_to_lng);
}
public CosDistance(double distance_meters) {
to_point = null;
sin_from_lat__sin_to_lat = 0;
cos_from_lat__cos_to_lat = 0;
sin_from_lng__sin_to_lng__cos_from_lng__cos_to_lng = 0;
cos_dist = Math.cos(distance_meters/RADIUS);
}
@Override
public int compareTo(CosDistance o) {
return  - Double.compare(cos_dist, o.cos_dist);
}
@Override
public int compareAxisTo(int axis, CosDistance o) {
return (0==axis)
?( - Double.compare(cos_dist, o.sin_from_lat__sin_to_lat + o.cos_from_lat__cos_to_lat)) // same longitude
:( - Double.compare(cos_dist, 1.0 + o.to_point.cos_lat*o.to_point.cos_lat*(o.sin_from_lng__sin_to_lng__cos_from_lng__cos_to_lng - 1.0))); // same latitude
}
@Override
public LatLngCommon getToPoint() {
return to_point;
}
}


Providing your own implementations of Metric and Distance interfaces you can easily calculate closest point in different coordinates (e.g. Cartesian).

Finding N-closest point example is available here. Number of points to be searched can be specified as get method parameter "number".


Last point is to solve problem stated a little differently - find all points within specified range. You can find in "CosDistance" definition additional constructor (with one double argument - distance) and Earth radius used in Google maps (see green code above).
Such distance calculated from radius in meters is required for finding points in range method:

private void findInRange(PointNode<P> root, P point, D range, int depth, CheckedArrayList<D> results) {

D distance = point.getDistance(root.point);

if (root.left == null && root.right == null) {
results.addChecked(distance);
return;
}

final int axis = depth % 2;
boolean left = false;

if ((root.left != null) && (point.compareAxisTo(axis, root.point) < 0)) {
findInRange(root.left, point, range, depth+1, results);
left = true;
}
else if (root.right != null) {
findInRange(root.right, point, range, depth+1, results);
}

results.addChecked(distance);

if (range.compareAxisTo(axis, distance) >= 0) {
if (left) {
if (root.right != null) {
findInRange(root.right, point, range, depth+1, results);
}
}
else {
if (root.left != null) {
findInRange(root.left, point, range, depth+1, results);
}
}
}
}

As you can see this method is almost the same as finding nearest points. There are two important differences:

• first - container used for results storage - now we use CheckedArrayList - number of elements stored is not limited, but point is only added if its distance is lower than llimit,
• second - searching different branch of a tree is performed only when actual distance along actual axis is smaller than given distance (range).

CheckedArrayList is thus implemented as simple extension of ArrayList:

private static class CheckedArrayList<T extends Comparable<T>> extends ArrayList<T> {
T reference;
public CheckedArrayList(T ref) {
reference = ref;
}
   public void addChecked(T value) {
      if (value.compareTo(reference) < 0) {
       add(value);
      }
   }
}

Finding points in range example is available here. Radius for search can be specified as get method parameter "radius".

All the code presented above you can find here.