- Made a function from the ME_TO_DOUBLE() macro (in src/mantissa.h).
authorBernd Petrovitsch <bernd@firmix.at>
Tue, 28 Aug 2007 20:45:17 +0000 (20:45 +0000)
committerBernd Petrovitsch <bernd@firmix.at>
Tue, 28 Aug 2007 20:45:17 +0000 (20:45 +0000)
  This saves code throughout the code even on i386 and will even more
  on architectures without floating point units and "-msoft-float".
- And the mathemathics in src/mantissa.h is reformulated to minimize
  floating point operations to save CPU power - especially on embedded
  devices.

CHANGELOG
lib/nameservice/src/nameservice.c
src/lq_packet.c
src/mantissa.c
src/mantissa.h
src/print_packet.c
src/rebuild_packet.c

index 34791ed..8355401 100644 (file)
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,5 +1,5 @@
 This file states changes as of version 0.2.4:
-$Id: CHANGELOG,v 1.76 2007/08/25 19:51:14 bernd67 Exp $
+$Id: CHANGELOG,v 1.77 2007/08/28 20:45:17 bernd67 Exp $
 
 0.5.4 ---------------------------------------------------------------------
 
@@ -35,6 +35,14 @@ olsr_makefile_make_use_of_exename.patch
 - This patch makes sure that the EXENAME variable of Makefile.inc is used
   in Makefile.
 
+PATCH by Bernd Petrovitsch <bernd@firmix.at>
+- Made a function from the ME_TO_DOUBLE() macro (in src/mantissa.h).
+  This saves code throughout the code even on i386 and will even more
+  on architectures without floating point units and "-msoft-float".
+- And the mathemathics in src/mantissa.h is reformulated to minimize
+  floating point operations to save CPU power - especially on embedded
+  devices.
+
 CLEANUPS
 - paving the way to activate -Wshadow, much more to do
 - const-ify parameters here and there
index 932f94e..7196588 100644 (file)
@@ -31,7 +31,7 @@
  *
  */
 
-/* $Id: nameservice.c,v 1.26 2007/08/25 19:48:42 bernd67 Exp $ */
+/* $Id: nameservice.c,v 1.27 2007/08/28 20:45:17 bernd67 Exp $ */
 
 /*
  * Dynamic linked library for UniK OLSRd
@@ -613,12 +613,12 @@ olsr_parser(union olsr_message *m, struct interface *in_if, union olsr_ip_addr *
                
        /* Fetch the message based on IP version */
        if(olsr_cnf->ip_version == AF_INET) {
-               vtime = ME_TO_DOUBLE(m->v4.olsr_vtime);
+               vtime = me_to_double(m->v4.olsr_vtime);
                size = ntohs(m->v4.olsr_msgsize);
                namemessage = (struct namemsg*)&m->v4.message;
        }
        else {
-               vtime = ME_TO_DOUBLE(m->v6.olsr_vtime);
+               vtime = me_to_double(m->v6.olsr_vtime);
                size = ntohs(m->v6.olsr_msgsize);
                namemessage = (struct namemsg*)&m->v6.message;
        }
index ed22508..7984256 100644 (file)
@@ -38,7 +38,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_packet.c,v 1.25 2007/08/19 20:37:41 bernd67 Exp $
+ * $Id: lq_packet.c,v 1.26 2007/08/28 20:45:17 bernd67 Exp $
  */
 
 #include "olsr_protocol.h"
@@ -69,7 +69,7 @@ create_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
   // initialize the static fields
 
   lq_hello->comm.type = LQ_HELLO_MESSAGE;
-  lq_hello->comm.vtime = ME_TO_DOUBLE(outif->valtimes.hello);
+  lq_hello->comm.vtime = me_to_double(outif->valtimes.hello);
   lq_hello->comm.size = 0;
 
   COPY_IP(&lq_hello->comm.orig, &olsr_cnf->main_addr);
@@ -160,7 +160,7 @@ create_lq_tc(struct lq_tc_message *lq_tc, struct interface *outif)
   // initialize the static fields
 
   lq_tc->comm.type = LQ_TC_MESSAGE;
-  lq_tc->comm.vtime = ME_TO_DOUBLE(outif->valtimes.tc);
+  lq_tc->comm.vtime = me_to_double(outif->valtimes.tc);
   lq_tc->comm.size = 0;
 
   COPY_IP(&lq_tc->comm.orig, &olsr_cnf->main_addr);
@@ -579,7 +579,7 @@ static void *deserialize_common(struct olsr_common *comm, void *ser)
       olsr_head_v4 = (struct olsr_header_v4 *)ser;
 
       comm->type = olsr_head_v4->type;
-      comm->vtime = ME_TO_DOUBLE(olsr_head_v4->vtime);
+      comm->vtime = me_to_double(olsr_head_v4->vtime);
       comm->size = ntohs(olsr_head_v4->size);
 
       COPY_IP(&comm->orig, &olsr_head_v4->orig);
@@ -596,7 +596,7 @@ static void *deserialize_common(struct olsr_common *comm, void *ser)
   olsr_head_v6 = (struct olsr_header_v6 *)ser;
 
   comm->type = olsr_head_v6->type;
-  comm->vtime = ME_TO_DOUBLE(olsr_head_v6->vtime);
+  comm->vtime = me_to_double(olsr_head_v6->vtime);
   comm->size = ntohs(olsr_head_v6->size);
 
   COPY_IP(&comm->orig, &olsr_head_v6->orig);
@@ -629,7 +629,7 @@ deserialize_lq_hello(struct lq_hello_message *lq_hello, void *ser)
 
   limit = ((unsigned char *)ser) + lq_hello->comm.size;
 
-  lq_hello->htime = ME_TO_DOUBLE(head->htime);
+  lq_hello->htime = me_to_double(head->htime);
   lq_hello->will = head->will;
 
   lq_hello->neigh = NULL;
index 6631282..0bc1ee0 100644 (file)
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: mantissa.c,v 1.8 2005/05/25 13:36:26 kattemat Exp $
+ * $Id: mantissa.c,v 1.9 2007/08/28 20:45:17 bernd67 Exp $
  */
 
-
 #include "mantissa.h"
 
 /**
  */
 
 olsr_u8_t
-double_to_me(double interval)
+double_to_me(const double interval)
 {
-  olsr_u8_t a, b;
-
-  b = 0;
+    olsr_u8_t a, b;
 
-  while(interval / VTIME_SCALE_FACTOR >= (1<<b))
-    b++;
+    /* It is sufficent to compare the integer part since we test on >=.
+     * So we have now only a floating point division and the rest of the loop
+     * are only integer operations.
+     */
+    const unsigned int unscaled_interval = interval / VTIME_SCALE_FACTOR;
+    b = 0;
+    while (unscaled_interval >= (1U << b)) {
+        b++;
+    }
 
-  if(b == 0)
-    {
-      a = 1;
-      b = 0;
-    } 
-  else 
-    {
-      b--;
-      if (b > 15)
-       {
-         a = 15;
-         b = 15;
-       } 
-      else 
-       { 
-         a = (int)(16*((double)interval/(VTIME_SCALE_FACTOR*(double)(1<<b))-1));
-         while(a >= 16)
-           {
-             a -= 16;
-             b++;
-           }
-       }
+    if(b == 0) {
+        a = 1;
+        b = 0;
+    } else {
+        b--;
+        if (b > 15) {
+            a = 15;
+            b = 15;
+        } else {
+            /* And again some maths simplification from the former version:
+             *    a = 16 * ((double)interval / (VTIME_SCALE_FACTOR * (double)(1 << b)) - 1)
+             * Since interval is already double:
+             *    a = 16 * (interval / (VTIME_SCALE_FACTOR * (double)(1 << b)) - 1)
+             * first, we can get rid of parentheses and change the * to a /
+             *    a = 16 * (interval / VTIME_SCALE_FACTOR / (double)(1 << b) - 1)
+             * then we make an integer addition from the floating point addition
+             *    a = (int)(16.0 * interval / VTIME_SCALE_FACTOR / (double)(1 << b)) - 16
+             * and we loose an unnecessary cast
+             *    a = (int)(16.0 * interval / VTIME_SCALE_FACTOR / (1 << b)) - 16
+             */
+            a = (int)(16.0 * interval / VTIME_SCALE_FACTOR / (1 << b)) - 16;
+            b += a >> 4;
+            a &= 0x0f;
+        }
     }
-  //printf("Generated mantissa/exponent(%d/%d): %d from %f\n", a, b, (olsr_u8_t) (a*16+b), interval);  //printf("Resolves back to: %f\n", ME_TO_DOUBLE(((a<<4)|(b&0x0F))));
-  return (olsr_u8_t) ((a<<4)|(b&0x0F));
+    //printf("Generated mantissa/exponent(%d/%d): %d from %f\n", a, b, (olsr_u8_t) (a*16+b), interval);  //printf("Resolves back to: %f\n", me_to_double(((a<<4)|(b&0x0F))));
+    return (a << 4) | (b & 0x0F);
+}
+
+/**
+ * Function for converting a mantissa/exponent 8bit value back
+ * to double as described in RFC3626:
+ *
+ * value = C*(1+a/16)*2^b [in seconds]
+ *
+ *  where a is the integer represented by the four highest bits of the
+ *  field and b the integer represented by the four lowest bits of the
+ *  field.
+ *
+ * me is the 8 bit mantissa/exponent value
+ *
+ * To avoid expensive floating maths, we transform the equation:
+ *     value = C * (1 + a / 16) * 2^b
+ * first, we make an int addition from the floating point addition:
+ *     value = C * ((16 + a) / 16) * 2^b
+ * then we get rid of a pair of parentheses
+ *     value = C * (16 + a) / 16 * 2^b
+ * and now we make an int multiplication from the floating point one
+ *     value = C * (16 + a) * 2^b / 16
+ * so that we can make a shift from the multiplication
+ *     value = C * ((16 + a) << b) / 16
+ * and sionce C and 16 are constants
+ *     value = ((16 + a) << b) * C / 16
+ */
+double me_to_double(const olsr_u8_t me)
+{
+    const olsr_u8_t a = me >> 4;
+    const olsr_u8_t b = me & 0x0F;
+    return ((16 + a) << b) * VTIME_SCALE_FACTOR / 16.0;
 }
index 45469e2..b91870b 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: mantissa.h,v 1.9 2005/05/29 12:47:45 br1 Exp $
+ * $Id: mantissa.h,v 1.10 2007/08/28 20:45:17 bernd67 Exp $
  */
 
 
  * me is the 8 bit mantissa/exponent value
  *
  */
-#define ME_TO_DOUBLE(me) \
-  (double)(VTIME_SCALE_FACTOR*(1+(double)(me>>4)/16)*(double)(1<<(me&0x0F)))
+double me_to_double(const olsr_u8_t);
 
-olsr_u8_t
-double_to_me(double);
+olsr_u8_t double_to_me(const double);
 
 #endif
index 9005143..f48fd9d 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: print_packet.c,v 1.10 2007/04/22 20:25:48 bernd67 Exp $
+ * $Id: print_packet.c,v 1.11 2007/08/28 20:45:17 bernd67 Exp $
  */
 
 #include "print_packet.h"
@@ -109,7 +109,7 @@ print_olsr_serialized_message(FILE *handle, union olsr_message *msg)
   fprintf(handle, "    Type: %s, size: %d, vtime: %0.2f\n", 
          olsr_msgtype_to_string(msg->v4.olsr_msgtype), 
          ntohs(msg->v4.olsr_msgsize),
-         ME_TO_DOUBLE(msg->v4.olsr_vtime));
+         me_to_double(msg->v4.olsr_vtime));
   fprintf(handle, "    TTL: %d, Hopcnt: %d, seqno: %d\n",
          (olsr_cnf->ip_version == AF_INET) ? msg->v4.ttl : msg->v6.ttl,
          (olsr_cnf->ip_version == AF_INET) ? msg->v4.hopcnt : msg->v6.hopcnt,
@@ -192,7 +192,7 @@ print_hellomsg(FILE *handle, olsr_u8_t *data, olsr_16_t totsize)
   union olsr_ip_addr *haddr;
   int hellosize = totsize - ((olsr_cnf->ip_version == AF_INET) ? OLSR_MSGHDRSZ_IPV4 : OLSR_MSGHDRSZ_IPV6);
 
-  fprintf(handle, "    +Htime: %0.2f\n", ME_TO_DOUBLE(data[2]));
+  fprintf(handle, "    +Htime: %0.2f\n", me_to_double(data[2]));
 
   fprintf(handle, "    +Willingness: %d\n", data[3]);
 
@@ -259,7 +259,7 @@ print_hellomsg_lq(FILE *handle, olsr_u8_t *data, olsr_16_t totsize)
   union olsr_ip_addr *haddr;
   int hellosize = totsize - ((olsr_cnf->ip_version == AF_INET) ? OLSR_MSGHDRSZ_IPV4 : OLSR_MSGHDRSZ_IPV6);
 
-  fprintf(handle, "    +Htime: %0.2f\n", ME_TO_DOUBLE(data[2]));
+  fprintf(handle, "    +Htime: %0.2f\n", me_to_double(data[2]));
 
   fprintf(handle, "    +Willingness: %d\n", data[3]);
 
index ed9a41d..ae917a7 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: rebuild_packet.c,v 1.21 2007/04/25 22:08:13 bernd67 Exp $
+ * $Id: rebuild_packet.c,v 1.22 2007/08/28 20:45:17 bernd67 Exp $
  */
 
 
@@ -87,7 +87,7 @@ hna_chgestruct(struct hna_message *hmsg, union olsr_message *m)
       //printf("HNA from %s\n\n", olsr_ip_to_string((union olsr_ip_addr *)&hmsg->originator));
 
       /* Get vtime */
-      hmsg->vtime = ME_TO_DOUBLE(m->v4.olsr_vtime);
+      hmsg->vtime = me_to_double(m->v4.olsr_vtime);
 
       tmp_pairs = NULL;
       hna_pairs = NULL;
@@ -127,7 +127,7 @@ hna_chgestruct(struct hna_message *hmsg, union olsr_message *m)
       hmsg->hop_count =  m->v6.hopcnt;
       
       /* Get vtime */
-      hmsg->vtime = ME_TO_DOUBLE(m->v6.olsr_vtime);
+      hmsg->vtime = me_to_double(m->v6.olsr_vtime);
       
       tmp_pairs = NULL;
       hna_pairs = NULL;
@@ -212,7 +212,7 @@ mid_chgestruct(struct mid_message *mmsg, union olsr_message *m)
       mmsg->mid_addr = NULL;
 
       /* Get vtime */
-      mmsg->vtime = ME_TO_DOUBLE(m->v4.olsr_vtime);
+      mmsg->vtime = me_to_double(m->v4.olsr_vtime);
 
       //printf("Sequencenuber of MID from %s is %d\n", ip_to_string(&mmsg->addr), mmsg->mid_seqno);
 
@@ -262,7 +262,7 @@ mid_chgestruct(struct mid_message *mmsg, union olsr_message *m)
       mmsg->mid_addr = NULL;
 
       /* Get vtime */
-      mmsg->vtime = ME_TO_DOUBLE(m->v6.olsr_vtime);
+      mmsg->vtime = me_to_double(m->v6.olsr_vtime);
 
       //printf("Sequencenuber of MID from %s is %d\n", ip_to_string(&mmsg->addr), mmsg->mid_seqno);
 
@@ -373,10 +373,10 @@ hello_chgestruct(struct hello_message *hmsg, union olsr_message *m)
 
 
       /* Get vtime */
-      hmsg->vtime = ME_TO_DOUBLE(m->v4.olsr_vtime);
+      hmsg->vtime = me_to_double(m->v4.olsr_vtime);
 
       /* Get htime */
-      hmsg->htime = ME_TO_DOUBLE(m->v4.message.hello.htime);
+      hmsg->htime = me_to_double(m->v4.message.hello.htime);
 
       /* Willingness */
       hmsg->willingness = m->v4.message.hello.willingness;
@@ -417,10 +417,10 @@ hello_chgestruct(struct hello_message *hmsg, union olsr_message *m)
       hmsg->packet_seq_number = ntohs(m->v6.seqno);
 
       /* Get vtime */
-      hmsg->vtime = ME_TO_DOUBLE(m->v6.olsr_vtime);
+      hmsg->vtime = me_to_double(m->v6.olsr_vtime);
 
       /* Get htime */
-      hmsg->htime = ME_TO_DOUBLE(m->v6.message.hello.htime);
+      hmsg->htime = me_to_double(m->v6.message.hello.htime);
 
       /* Willingness */
       hmsg->willingness = m->v6.message.hello.willingness;
@@ -496,7 +496,7 @@ tc_chgestruct(struct tc_message *tmsg, union olsr_message *m, union olsr_ip_addr
 
 
       /* Get vtime */
-      tmsg->vtime = ME_TO_DOUBLE(m->v4.olsr_vtime);
+      tmsg->vtime = me_to_double(m->v4.olsr_vtime);
 
       OLSR_PRINTF(3, "Got TC vtime: %f\n", tmsg->vtime);
 
@@ -538,7 +538,7 @@ tc_chgestruct(struct tc_message *tmsg, union olsr_message *m, union olsr_ip_addr
       /* Check if sender is symmetric neighbor here !! */
       
       /* Get vtime */
-      tmsg->vtime = ME_TO_DOUBLE(m->v6.olsr_vtime);
+      tmsg->vtime = me_to_double(m->v6.olsr_vtime);
 
       OLSR_PRINTF(3, "Got TC vtime: %f\n", tmsg->vtime);