Line data    Source code

       1             : #ifndef HEADER_fd_src_flamenco_runtime_program_vote_fd_validator_location_h
       2             : #define HEADER_fd_src_flamenco_runtime_program_vote_fd_validator_location_h
       3             : 
       4             : #include "../../../fd_flamenco_base.h"
       5             : 
       6             : /* fd_validator_location_t is the self-reported location of a
       7             :    validator, as described in SIMD-0674.
       8             : 
       9             :    A location is a WGS84 ECEF "Earth-Centered, Earth-Fixed" point
      10             :    in meters, measured from the center of the Earth. See
      11             :    https://en.wikipedia.org/wiki/Earth-centered,_Earth-fixed_coordinate_system
      12             : 
      13             :                   +z (North Pole)
      14             :                    |
      15             :                    |    . (x,y,z)
      16             :                    |   /
      17             :                    |  /
      18             :                    O------------ +y (equator, 90E)
      19             :                   /
      20             :                  /
      21             :                +x (equator, 0E)
      22             : 
      23             :    Validators are required to report the ECEF point on the Earth's
      24             :    surface directly below them, about 6400km from the center.  Their
      25             :    height above the surface should be set to 0:
      26             : 
      27             :                validator
      28             :                    o
      29             :                    |   height h (= 0)
      30             :          ----------*----------  the Earth's surface
      31             :                    ^
      32             :                    reported location
      33             : 
      34             :    To get this point:
      35             : 
      36             :      1. Look up the validator's latitude and longitude.
      37             :      2. Convert them to (x,y,z) with height h = 0, using a GPS library
      38             :         or an online converter such as
      39             :         https://geodesy.noaa.gov/TOOLS/XYZ/xyz.shtml
      40             :      3. Round x, y and z to the nearest meter.
      41             : 
      42             :    The conversion with h = 0:
      43             :      N = r / sqrt( 1 - e2*sin(lat)^2 )      r  = 6378137
      44             :                                             e2 = 0.00669437999014
      45             :      x = round( (N+h)        * cos(lat) * cos(lon) )
      46             :      y = round( (N+h)        * cos(lat) * sin(lon) )
      47             :      z = round( (N*(1-e2)+h) * sin(lat) )
      48             : 
      49             :    Frankfurt (50.11N, 8.68E) is (4051542, 618526, 4870645).
      50             : 
      51             :    See below for how we validate that the ECEF point reported is a
      52             :    valid point on the Earth's surface. */
      53             : 
      54             : struct fd_validator_location {
      55             :   int x;
      56             :   int y;
      57             :   int z;
      58             : };
      59             : typedef struct fd_validator_location fd_validator_location_t;
      60             : 
      61             : /* A self-reported location is valid if it describes a point on the
      62             :    Earth's surface (not above - in space - or below - underground).
      63             :    Here the Earth's surface is defined as being the WGS84 ellipsoid,
      64             :    which is roughly sea level. The criteria for checking this are
      65             :    defined in SIMD-0674 and explained below.
      66             : 
      67             :    The Earth is not a perfect sphere, but slightly flattened. It is
      68             :    about 43km wider at the equator than at the poles.
      69             :    Cut in half through the poles:
      70             : 
      71             :                                z
      72             :                                |
      73             :              +-----------------+-----------------+  <- COORD_MAX
      74             :              |        ..--'''''|'''''--..        |
      75             :              |    .-''         b         ''-.    |
      76             :              |  .'             |             '.  |
      77             :              | /               |               \ |
      78             :         -----+-----------------O-------r-------+-----> x, y
      79             :              | \               |               / |
      80             :              |  '.             |             .'  |
      81             :              |    '-..         |         ..-'    |
      82             :              |        ''--.....|.....--''        |
      83             :              +-----------------+-----------------+
      84             : 
      85             :      r = 6378137m, the radius at the equator
      86             :      b = 6356752m, the radius at the poles
      87             : 
      88             :    To check that a location is indeed a point on the Earth's surface,
      89             :    we don't want to do floating point trigonometry, so we instead
      90             :    stretch the Earth into a perfect sphere, and then a simple integer
      91             :    magnitude check works for all points:
      92             :    - Stretch z slightly (FLATTENING_CORRECTION), which turns the
      93             :      flattened Earth into an almost perfect sphere of radius r.
      94             :    - Check that the stretched point is within a +-1km SURFACE_TOLERANCE
      95             :      above or below the Earth's surface (SURFACE_DIST2).
      96             : 
      97             :          too low                 valid                too high
      98             :        <---------|=================|=================|--------->  dist2
      99             :            SURFACE_DIST2     SURFACE_DIST2     SURFACE_DIST2
     100             :         - SURFACE_TOLERANCE                 + SURFACE_TOLERANCE
     101             :              1km below          ground           1km above
     102             : 
     103             :    Example: Frankfurt is at (4051542, 618526, 4870645).  Every
     104             :    coordinate is within COORD_MAX (6378138), and:
     105             : 
     106             :        x^2                                   16414992577764
     107             :      + y^2                                     382574412676
     108             :      + z^2                                   23723182716025
     109             :      + (FLATTENING_CORRECTION * z^2) >> 16     159998272102
     110             :      ------------------------------------------------------
     111             :      = dist2                                 40680747978567
     112             :      - SURFACE_DIST2                         40680631590769
     113             :      ------------------------------------------------------
     114             :      = difference                                 116387798
     115             : 
     116             :    116387798 is less than SURFACE_TOLERANCE (12756274000), so Frankfurt
     117             :    is valid.  A point 2km higher, (4052815, 618720, 4872175), is
     118             :    25680309853 away, which is too far:
     119             : 
     120             :          too low                 valid                too high
     121             :        <---------|=================|=================|--------->  dist2
     122             :                                    ^                     ^
     123             :                                Frankfurt             2km above
     124             :                                                      Frankfurt */
     125           0 : #define FD_VALIDATOR_LOCATION_SURFACE_DIST2         (40680631590769UL)
     126           0 : #define FD_VALIDATOR_LOCATION_FLATTENING_CORRECTION (442UL)
     127           0 : #define FD_VALIDATOR_LOCATION_SURFACE_TOLERANCE     (12756274000UL)
     128             : 
     129             : /* The largest allowed magnitude of each coordinate: the Earth's radius
     130             :    at the equator (6378137m) plus 1m. */
     131             : 
     132           0 : #define FD_VALIDATOR_LOCATION_COORD_MAX (6378138)
     133             : 
     134             : FD_PROTOTYPES_BEGIN
     135             : 
     136             : /* Returns the squared distance of loc from the center of the Earth,
     137             :    with the flattening correction as described above, treating the
     138             :    Earth as a perfect sphere.
     139             : 
     140             :    Assumes every coordinate is no larger than
     141             :    FD_VALIDATOR_LOCATION_COORD_MAX. */
     142             : FD_FN_PURE static inline ulong
     143           0 : fd_validator_location_dist2_on_sphere( fd_validator_location_t const * loc ) {
     144           0 :   ulong x2 = (ulong)( (long)loc->x*(long)loc->x );
     145           0 :   ulong y2 = (ulong)( (long)loc->y*(long)loc->y );
     146           0 :   ulong z2 = (ulong)( (long)loc->z*(long)loc->z );
     147           0 :   return x2 + y2 + z2 + ( ( FD_VALIDATOR_LOCATION_FLATTENING_CORRECTION*z2 )>>16 );
     148           0 : }
     149             : 
     150             : /* Returns 1 if loc is a valid location on the Earth's surface,
     151             :    0 otherwise. */
     152             : FD_FN_PURE static inline int
     153           0 : fd_validator_location_is_valid( fd_validator_location_t const * loc ) {
     154           0 :   if( FD_UNLIKELY( loc->x<-FD_VALIDATOR_LOCATION_COORD_MAX || loc->x>FD_VALIDATOR_LOCATION_COORD_MAX ||
     155           0 :                    loc->y<-FD_VALIDATOR_LOCATION_COORD_MAX || loc->y>FD_VALIDATOR_LOCATION_COORD_MAX ||
     156           0 :                    loc->z<-FD_VALIDATOR_LOCATION_COORD_MAX || loc->z>FD_VALIDATOR_LOCATION_COORD_MAX ) ) return 0;
     157           0 :   ulong dist2 = fd_validator_location_dist2_on_sphere( loc );
     158           0 :   return dist2>=FD_VALIDATOR_LOCATION_SURFACE_DIST2-FD_VALIDATOR_LOCATION_SURFACE_TOLERANCE &&
     159           0 :          dist2<=FD_VALIDATOR_LOCATION_SURFACE_DIST2+FD_VALIDATOR_LOCATION_SURFACE_TOLERANCE;
     160           0 : }
     161             : 
     162             : FD_FN_PURE static inline ulong
     163             : fd_validator_location_dist2( fd_validator_location_t const * a,
     164           0 :                              fd_validator_location_t const * b ) {
     165           0 :   long dx = (long)a->x - (long)b->x;
     166           0 :   long dy = (long)a->y - (long)b->y;
     167           0 :   long dz = (long)a->z - (long)b->z;
     168           0 :   return (ulong)( dx*dx ) + (ulong)( dy*dy ) + (ulong)( dz*dz );
     169           0 : }
     170             : 
     171             : FD_PROTOTYPES_END
     172             : 
     173             : #endif /* HEADER_fd_src_flamenco_runtime_program_vote_fd_validator_location_h */