From a1faefc83a4b40f2562545e4efea7a9f5531a598 Mon Sep 17 00:00:00 2001 From: kaisenl Date: Tue, 18 Dec 2007 07:03:18 +0000 Subject: [PATCH] Initial checkin for DIP --- tos/lib/net/dip/AMDIPC.nc | 29 ++ tos/lib/net/dip/AMDIPP.nc | 90 ++++++ tos/lib/net/dip/DIP.h | 74 +++++ tos/lib/net/dip/DIPDataC.nc | 27 ++ tos/lib/net/dip/DIPDataP.nc | 107 +++++++ tos/lib/net/dip/DIPLogicC.nc | 48 +++ tos/lib/net/dip/DIPLogicP.nc | 297 ++++++++++++++++++ tos/lib/net/dip/DIPSummaryC.nc | 22 ++ tos/lib/net/dip/DIPSummaryP.nc | 271 ++++++++++++++++ tos/lib/net/dip/DIPTrickleMilliC.nc | 62 ++++ tos/lib/net/dip/DIPTrickleMilliP.nc | 120 +++++++ tos/lib/net/dip/DIPVectorC.nc | 23 ++ tos/lib/net/dip/DIPVectorP.nc | 142 +++++++++ tos/lib/net/dip/DIPVersionC.nc | 14 + tos/lib/net/dip/DIPVersionP.nc | 107 +++++++ tos/lib/net/dip/DisseminationC.nc | 11 + tos/lib/net/dip/DisseminatorC.nc | 77 +++++ tos/lib/net/dip/DisseminatorP.nc | 107 +++++++ tos/lib/net/dip/README | 27 ++ tos/lib/net/dip/interfaces/DIPDecision.nc | 6 + tos/lib/net/dip/interfaces/DIPEstimates.nc | 15 + tos/lib/net/dip/interfaces/DIPHelp.nc | 12 + tos/lib/net/dip/interfaces/DIPReceive.nc | 4 + tos/lib/net/dip/interfaces/DIPSend.nc | 6 + tos/lib/net/dip/interfaces/DIPTrickleTimer.nc | 88 ++++++ tos/lib/net/dip/interfaces/DIPVersion.nc | 7 + tos/lib/net/dip/qsort.c | 151 +++++++++ 27 files changed, 1944 insertions(+) create mode 100644 tos/lib/net/dip/AMDIPC.nc create mode 100644 tos/lib/net/dip/AMDIPP.nc create mode 100644 tos/lib/net/dip/DIP.h create mode 100644 tos/lib/net/dip/DIPDataC.nc create mode 100644 tos/lib/net/dip/DIPDataP.nc create mode 100644 tos/lib/net/dip/DIPLogicC.nc create mode 100644 tos/lib/net/dip/DIPLogicP.nc create mode 100644 tos/lib/net/dip/DIPSummaryC.nc create mode 100644 tos/lib/net/dip/DIPSummaryP.nc create mode 100644 tos/lib/net/dip/DIPTrickleMilliC.nc create mode 100644 tos/lib/net/dip/DIPTrickleMilliP.nc create mode 100644 tos/lib/net/dip/DIPVectorC.nc create mode 100644 tos/lib/net/dip/DIPVectorP.nc create mode 100644 tos/lib/net/dip/DIPVersionC.nc create mode 100644 tos/lib/net/dip/DIPVersionP.nc create mode 100644 tos/lib/net/dip/DisseminationC.nc create mode 100644 tos/lib/net/dip/DisseminatorC.nc create mode 100644 tos/lib/net/dip/DisseminatorP.nc create mode 100644 tos/lib/net/dip/README create mode 100644 tos/lib/net/dip/interfaces/DIPDecision.nc create mode 100644 tos/lib/net/dip/interfaces/DIPEstimates.nc create mode 100644 tos/lib/net/dip/interfaces/DIPHelp.nc create mode 100644 tos/lib/net/dip/interfaces/DIPReceive.nc create mode 100644 tos/lib/net/dip/interfaces/DIPSend.nc create mode 100644 tos/lib/net/dip/interfaces/DIPTrickleTimer.nc create mode 100644 tos/lib/net/dip/interfaces/DIPVersion.nc create mode 100644 tos/lib/net/dip/qsort.c diff --git a/tos/lib/net/dip/AMDIPC.nc b/tos/lib/net/dip/AMDIPC.nc new file mode 100644 index 00000000..c1e05136 --- /dev/null +++ b/tos/lib/net/dip/AMDIPC.nc @@ -0,0 +1,29 @@ +#include + +configuration AMDIPC { + provides interface DIPSend; + provides interface DIPReceive as DataReceive; + provides interface DIPReceive as VectorReceive; + provides interface DIPReceive as SummaryReceive; +} + +implementation { + components AMDIPP; + components new AMSenderC(AM_DIP) as SendC; + components new AMReceiverC(AM_DIP) as ReceiveC; + + AMDIPP.NetAMSend -> SendC.AMSend; + AMDIPP.NetReceive -> ReceiveC.Receive; + + components MainC; + MainC.SoftwareInit -> AMDIPP.Init; + AMDIPP.Boot -> MainC; + + components ActiveMessageC; + AMDIPP.AMSplitControl -> ActiveMessageC; + + DIPSend = AMDIPP.DIPSend; + DataReceive = AMDIPP.DIPDataReceive; + VectorReceive = AMDIPP.DIPVectorReceive; + SummaryReceive = AMDIPP.DIPSummaryReceive; +} diff --git a/tos/lib/net/dip/AMDIPP.nc b/tos/lib/net/dip/AMDIPP.nc new file mode 100644 index 00000000..7900dfbf --- /dev/null +++ b/tos/lib/net/dip/AMDIPP.nc @@ -0,0 +1,90 @@ + +module AMDIPP { + provides interface Init; + + provides interface DIPSend; + provides interface DIPReceive as DIPDataReceive; + provides interface DIPReceive as DIPVectorReceive; + provides interface DIPReceive as DIPSummaryReceive; + + uses interface AMSend as NetAMSend; + uses interface Receive as NetReceive; + + uses interface SplitControl as AMSplitControl; + uses interface Boot; +} + +implementation { + message_t am_msg; + bool busy; + + event void Boot.booted() { + call AMSplitControl.start(); + } + + event void AMSplitControl.startDone(error_t err) { + if(err != SUCCESS) { + call AMSplitControl.start(); + return; + } + dbg("AMDIPP", "ActiveMessageC started!\n"); + } + + event void AMSplitControl.stopDone(error_t err) { } + + command error_t Init.init() { + busy = FALSE; + return SUCCESS; + } + + command error_t DIPSend.send(uint8_t len) { + error_t err; + dbg("AMDIPP", "Attempting to send data in the air\n"); + err = call NetAMSend.send(AM_BROADCAST_ADDR, &am_msg, len); + if(err == SUCCESS) { + busy = TRUE; + } + return err; + } + + command void* DIPSend.getPayloadPtr() { + // returns NULL if message is busy + if(busy) { + return NULL; + } + return call NetAMSend.getPayload(&am_msg, 0); + } + + command uint8_t DIPSend.maxPayloadLength() { + return call NetAMSend.maxPayloadLength(); + } + + event void NetAMSend.sendDone(message_t* msg, error_t err) { + dbg("AMDIPP", "Data send successfully in the air\n"); + if(msg == &am_msg) { + busy = FALSE; + } + } + + event message_t* NetReceive.receive(message_t* msg, void* payload, + uint8_t len) { + dip_msg_t* dmsg; + uint8_t type; + + dmsg = (dip_msg_t*) payload; + type = dmsg->type; + switch(type) { + case ID_DIP_DATA: + signal DIPDataReceive.receive(dmsg->content, len); + break; + case ID_DIP_VECTOR: + signal DIPVectorReceive.receive(dmsg->content, len); + break; + case ID_DIP_SUMMARY: + signal DIPSummaryReceive.receive(dmsg->content, len); + break; + } + return msg; + } + +} diff --git a/tos/lib/net/dip/DIP.h b/tos/lib/net/dip/DIP.h new file mode 100644 index 00000000..6d988607 --- /dev/null +++ b/tos/lib/net/dip/DIP.h @@ -0,0 +1,74 @@ + +#ifndef __DIP_H__ +#define __DIP_H__ + +#define DIP_TAU_LOW (1024L) +#define DIP_TAU_HIGH (65535L) + +#define UQ_DIP unique("DIP") +#define UQCOUNT_DIP uniqueCount("DIP") + +#define DIP_UNKNOWN_VERSION 0xFFFFFFFF +#define DIP_UNKNOWN_INDEX 0xFFFF + +typedef enum { + ID_DIP_INVALID = 0x0, + ID_DIP_SUMMARY = 0x1, + ID_DIP_VECTOR = 0x2, + ID_DIP_DATA = 0x3 +} dip_msgid_t; + +enum { + AM_DIP = 0x84 +}; + +typedef uint16_t dip_index_t; +typedef uint16_t dip_key_t; +typedef nx_uint16_t nx_dip_key_t; +typedef uint32_t dip_version_t; +typedef nx_uint32_t nx_dip_version_t; +typedef uint8_t dip_estimate_t; +typedef dip_index_t dip_hashlen_t; + +typedef nx_struct dip_msg_t { + nx_uint8_t type; // dip_msgid_t + nx_uint8_t content[0]; +} dip_msg_t; + +typedef nx_struct dip_data_msg_t { + nx_dip_key_t key; + nx_dip_version_t version; + nx_uint8_t size; + nx_uint8_t data[0]; +} dip_data_msg_t; + +typedef nx_struct dip_vector_msg_t { + nx_uint8_t unitLen; + nx_uint32_t vector[0]; +} dip_vector_msg_t; + +typedef nx_struct dip_summary_msg_t { + nx_uint8_t unitLen; + nx_uint32_t salt; + nx_uint32_t info[0]; +} dip_summary_msg_t; + +dip_estimate_t DIP_DATA_ESTIMATE; +dip_estimate_t DIP_MAX_ESTIMATE; +dip_estimate_t DIP_VECTOR_ESTIMATE; + +#define DIP_SUMMARY_ENTRIES_PER_PACKET (DIP_SUMMARY_VALUES_PER_PACKET * 3) +#define DIP_VECTOR_ENTRIES_PER_PACKET (DIP_VECTOR_VALUES_PER_PACKET * 2) + +#include "qsort.c" + +/* TUNABLE PARAMETERS */ + +typedef struct dip_data_t { + uint8_t data[16]; +} dip_data_t; + +#define DIP_SUMMARY_VALUES_PER_PACKET 2 +#define DIP_VECTOR_VALUES_PER_PACKET 2 + +#endif diff --git a/tos/lib/net/dip/DIPDataC.nc b/tos/lib/net/dip/DIPDataC.nc new file mode 100644 index 00000000..5f98992f --- /dev/null +++ b/tos/lib/net/dip/DIPDataC.nc @@ -0,0 +1,27 @@ + +configuration DIPDataC { + provides interface DIPDecision; + + uses interface DIPSend as DataSend; + uses interface DIPReceive as DataReceive; + + uses interface DisseminationUpdate[dip_key_t key]; + uses interface DisseminationValue[dip_key_t key]; + + uses interface DIPHelp; + uses interface DIPEstimates; +} + +implementation { + components DIPDataP; + DIPDecision = DIPDataP; + DataSend = DIPDataP; + DataReceive = DIPDataP; + DisseminationUpdate = DIPDataP; + DisseminationValue = DIPDataP; + DIPHelp = DIPDataP; + DIPEstimates = DIPDataP; + + components LedsC; + DIPDataP.Leds -> LedsC; +} diff --git a/tos/lib/net/dip/DIPDataP.nc b/tos/lib/net/dip/DIPDataP.nc new file mode 100644 index 00000000..02a14b53 --- /dev/null +++ b/tos/lib/net/dip/DIPDataP.nc @@ -0,0 +1,107 @@ + +#include + +module DIPDataP { + provides interface DIPDecision; + + uses interface DIPSend as DataSend; + uses interface DIPReceive as DataReceive; + + uses interface DisseminationUpdate[dip_key_t key]; + uses interface DisseminationValue[dip_key_t key]; + + uses interface DIPHelp; + uses interface DIPEstimates; + + uses interface Leds; +} + +implementation { + uint8_t commRate = 0; + + command uint8_t DIPDecision.getCommRate() { + return commRate; + } + + command void DIPDecision.resetCommRate() { + commRate = 0; + } + + command error_t DIPDecision.send() { + // Scan all estimates and send the highest estimate in deterministic order + dip_index_t i; + dip_index_t high_i; + dip_index_t high_est; + dip_key_t key; + dip_version_t ver; + dip_estimate_t* ests; + dip_msg_t* dmsg; + dip_data_msg_t* ddmsg; + const dip_data_t* data; + + ests = call DIPEstimates.getEstimates(); + high_i = 0; + high_est = 0; + for(i = 0; i < UQCOUNT_DIP; i++) { + if(ests[i] > high_est) { + high_i = i; + high_est = ests[i]; + } + } + key = call DIPHelp.indexToKey(high_i); + ver = call DIPHelp.keyToVersion(key); + data = call DisseminationValue.get[key](); + dmsg = (dip_msg_t*) call DataSend.getPayloadPtr(); + if(dmsg == NULL) { + return FAIL; + } + ddmsg = (dip_data_msg_t*) dmsg->content; + dmsg->type = ID_DIP_DATA; + + ddmsg->key = key; + ddmsg->version = ver; + ddmsg->size = sizeof(dip_data_t); + memcpy(ddmsg->data, data, sizeof(dip_data_t)); + + call DIPEstimates.decEstimateByKey(key); + dbg("DIPDataP", "Data sent with key %x and version %08x\n", key, ver); + return call DataSend.send(sizeof(dip_data_msg_t) + sizeof(dip_msg_t) + sizeof(dip_data_t)); + } + + event void DataReceive.receive(void* payload, uint8_t len) { + dip_key_t key; + dip_version_t myVer; + dip_version_t msgVer; + dip_data_msg_t* ddmsg; + + commRate = commRate + 1; + + ddmsg = (dip_data_msg_t*) payload; + key = ddmsg->key; + msgVer = ddmsg->version; + myVer = call DIPHelp.keyToVersion(key); + dbg("DIPDataP", "Data rcved with key %x and version %08x\n", key, msgVer); + + // TODO: handle the invalid versions + if(myVer < msgVer) { + call DisseminationUpdate.change[key]((dip_data_t*)ddmsg->data); + call DIPHelp.setVersion(key, msgVer); + call DIPEstimates.setDataEstimate(key); + } + else if (myVer > msgVer) { + call DIPEstimates.setDataEstimate(key); + } + else { + call DIPEstimates.decEstimateByKey(key); + } + } + + event void DisseminationValue.changed[dip_key_t key]() { } + + default command const dip_data_t* DisseminationValue.get[dip_key_t key]() { + return NULL; + } + + default command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) { } + +} diff --git a/tos/lib/net/dip/DIPLogicC.nc b/tos/lib/net/dip/DIPLogicC.nc new file mode 100644 index 00000000..5f849367 --- /dev/null +++ b/tos/lib/net/dip/DIPLogicC.nc @@ -0,0 +1,48 @@ + +#include + +configuration DIPLogicC { + provides interface DisseminationUpdate[dip_key_t key]; + + provides interface StdControl; +} + +implementation { + components DIPLogicP; + DisseminationUpdate = DIPLogicP; + StdControl = DIPLogicP; + + components MainC; + MainC.SoftwareInit -> DIPLogicP; + DIPLogicP.Boot -> MainC; + + components DIPTrickleMilliC; + DIPLogicP.DIPTrickleTimer -> DIPTrickleMilliC; + + components DIPVersionC; + DIPLogicP.VersionUpdate -> DIPVersionC; + DIPLogicP.DIPHelp -> DIPVersionC; + + components AMDIPC; + + components DIPDataC; + DIPLogicP.DIPDataDecision -> DIPDataC; + DIPDataC.DataSend -> AMDIPC.DIPSend; + DIPDataC.DataReceive -> AMDIPC.DataReceive; + DIPDataC.DIPHelp -> DIPVersionC; + DIPDataC.DIPEstimates -> DIPLogicP; + + components DIPVectorC; + DIPLogicP.DIPVectorDecision -> DIPVectorC; + DIPVectorC.VectorSend -> AMDIPC.DIPSend; + DIPVectorC.VectorReceive -> AMDIPC.VectorReceive; + DIPVectorC.DIPHelp -> DIPVersionC; + DIPVectorC.DIPEstimates -> DIPLogicP; + + components DIPSummaryC; + DIPLogicP.DIPSummaryDecision -> DIPSummaryC; + DIPSummaryC.SummarySend -> AMDIPC.DIPSend; + DIPSummaryC.SummaryReceive -> AMDIPC.SummaryReceive; + DIPSummaryC.DIPHelp -> DIPVersionC; + DIPSummaryC.DIPEstimates -> DIPLogicP; +} diff --git a/tos/lib/net/dip/DIPLogicP.nc b/tos/lib/net/dip/DIPLogicP.nc new file mode 100644 index 00000000..3fd52a61 --- /dev/null +++ b/tos/lib/net/dip/DIPLogicP.nc @@ -0,0 +1,297 @@ + +#include + +module DIPLogicP { + provides interface DisseminationUpdate[dip_key_t key]; + provides interface DIPEstimates; + + provides interface Init; + provides interface StdControl; + + uses interface Boot; + uses interface DIPTrickleTimer; + uses interface DisseminationUpdate as VersionUpdate[dip_key_t key]; + uses interface DIPDecision as DIPDataDecision; + uses interface DIPDecision as DIPVectorDecision; + uses interface DIPDecision as DIPSummaryDecision; + uses interface DIPHelp; +} + +implementation { + uint32_t windowSize; + dip_hashlen_t totalPossible; + + dip_estimate_t estimates[UQCOUNT_DIP]; + + uint16_t diplog(uint16_t base, uint16_t num); + uint16_t dipexp(uint16_t base, uint16_t expt); + dip_estimate_t getDataEstimate(dip_hashlen_t len); + dip_estimate_t getMaxEstimate(dip_hashlen_t len); + uint8_t sendDecision(); + + command error_t Init.init() { + windowSize = DIP_TAU_HIGH; + DIP_DATA_ESTIMATE = getDataEstimate(UQCOUNT_DIP); + DIP_MAX_ESTIMATE = getMaxEstimate(UQCOUNT_DIP); + DIP_VECTOR_ESTIMATE = DIP_DATA_ESTIMATE - 1; + totalPossible = call DIPEstimates.estimateToHashlength(0); + dbg("DIPLogicP", "Real Total: %u, DIP Total: %u\n", UQCOUNT_DIP, totalPossible); + if(totalPossible < UQCOUNT_DIP) { + DIP_DATA_ESTIMATE++; + DIP_MAX_ESTIMATE++; + DIP_VECTOR_ESTIMATE++; + totalPossible = call DIPEstimates.estimateToHashlength(0); + } + dbg("DIPLogicP", "Real Total: %u, DIP New Total: %u\n", UQCOUNT_DIP, totalPossible); + dbg("DIPLogicP","DATA_ESTIMATE initialized to %u\n", DIP_DATA_ESTIMATE); + dbg("DIPLogicP","MAX_ESTIMATE initialized to %u\n", DIP_MAX_ESTIMATE); + dbg("DIPLogicP","VECT_ESTIMATE initialized to %u\n", DIP_VECTOR_ESTIMATE); + dbg("DIPLogicP","DIP ready\n"); + + return SUCCESS; + } + + event void Boot.booted() { + + } + + command error_t StdControl.start() { + return call DIPTrickleTimer.start(); + } + + command error_t StdControl.stop() { + call DIPTrickleTimer.stop(); + return SUCCESS; + } + + command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) { + dip_index_t i; + + dbg("DIPLogicP","App notified key %x is new\n", key); + i = call DIPHelp.keyToIndex(key); + estimates[i] = DIP_DATA_ESTIMATE; + call VersionUpdate.change[key](val); + call DIPTrickleTimer.reset(); + } + + event uint32_t DIPTrickleTimer.requestWindowSize() { + dip_index_t i; + dip_estimate_t max = 0; + + for(i = 0; i < UQCOUNT_DIP; i++) { + if(estimates[i] > 0) { + max = estimates[i]; + windowSize = DIP_TAU_LOW; + break; + } + } + if(max == 0) { + windowSize = windowSize << 1; + if(windowSize > DIP_TAU_HIGH) { + windowSize = DIP_TAU_HIGH; + } + } + + dbg("DIPLogicP", "Window size requested, give %u\n", windowSize); + return windowSize; + } + + event void DIPTrickleTimer.fired() { + dip_index_t i; + uint8_t decision; + + dbg("DIPLogicP","Trickle Timer fired!\n"); + + for(i = 0; i < UQCOUNT_DIP; i++) { + dbg("DIPLogicP","Index-%u Estimate-%u\n", i, estimates[i]); + } + + decision = sendDecision(); + + switch(decision) { + case ID_DIP_INVALID: + dbg("DIPLogicP", "Decision to SUPPRESS\n"); + break; + case ID_DIP_SUMMARY: + dbg("DIPLogicP", "Decision to SUMMARY\n"); + call DIPSummaryDecision.send(); + break; + case ID_DIP_VECTOR: + dbg("DIPLogicP", "Decision to VECTOR\n"); + call DIPVectorDecision.send(); + break; + case ID_DIP_DATA: + dbg("DIPLogicP", "Decision to DATA\n"); + call DIPDataDecision.send(); + break; + } + call DIPDataDecision.resetCommRate(); + call DIPVectorDecision.resetCommRate(); + call DIPSummaryDecision.resetCommRate(); + } + + command dip_estimate_t* DIPEstimates.getEstimates() { + return estimates; + } + + command void DIPEstimates.decEstimateByIndex(dip_index_t i) { + if(estimates[i] != 0) { + estimates[i] = estimates[i] - 1; + } + } + + command void DIPEstimates.decEstimateByKey(dip_key_t key) { + dip_index_t i; + + i = call DIPHelp.keyToIndex(key); + call DIPEstimates.decEstimateByIndex(i); + } + + command dip_estimate_t DIPEstimates.hashlengthToEstimate(dip_hashlen_t len) { + if(len == UQCOUNT_DIP) { + len = totalPossible; + } + return DIP_MAX_ESTIMATE - diplog(DIP_SUMMARY_VALUES_PER_PACKET, len); + } + + command dip_hashlen_t DIPEstimates.estimateToHashlength(dip_estimate_t est) { + uint8_t expt, base; + uint16_t val; + + base = DIP_SUMMARY_VALUES_PER_PACKET; + expt = DIP_MAX_ESTIMATE - est; + val = dipexp(base, expt); + + if(val > UQCOUNT_DIP) { // bring length back down if over UQCOUNT_DIP + val = UQCOUNT_DIP; + } + + return val; + } + + /* Calculation functions */ + uint16_t diplog(uint16_t base, uint16_t num) { + uint8_t counter; + + counter = 0; + while(num != 0) { + num = num / base; + counter++; + } + return counter - 1; + } + + command void DIPEstimates.setDataEstimate(dip_key_t key) { + dip_index_t i; + + i = call DIPHelp.keyToIndex(key); + estimates[i] = DIP_DATA_ESTIMATE; + call DIPTrickleTimer.reset(); + } + + command void DIPEstimates.setVectorEstimate(dip_key_t key) { + dip_index_t i; + + i = call DIPHelp.keyToIndex(key); + if(estimates[i] < DIP_VECTOR_ESTIMATE) { + estimates[i] = DIP_VECTOR_ESTIMATE; + } + call DIPTrickleTimer.reset(); + } + + command void DIPEstimates.setSummaryEstimateByIndex(dip_index_t ind, + dip_estimate_t est) { + if(estimates[ind] < est) { + estimates[ind] = est; + } + call DIPTrickleTimer.reset(); + } + + uint16_t dipexp(uint16_t base, uint16_t expt) { + uint16_t ans; + + ans = 1; + while(expt > 0) { + if((expt & 1) == 0) { + base = base * base; + expt = expt >> 1; + } + else { + ans = ans * base; + expt = expt - 1; + } + } + return ans; + } + + dip_estimate_t getDataEstimate(dip_hashlen_t len) { + dip_estimate_t h_total; + dip_estimate_t v_total; + + h_total = diplog(DIP_SUMMARY_VALUES_PER_PACKET, len); + v_total = diplog(DIP_SUMMARY_VALUES_PER_PACKET, + DIP_VECTOR_VALUES_PER_PACKET); + + return h_total - v_total + 1; + } + + dip_estimate_t getMaxEstimate(dip_hashlen_t len) { + return diplog(DIP_SUMMARY_VALUES_PER_PACKET, len); + } + + uint8_t sendDecision() { + dip_estimate_t highEst; + dip_estimate_t est; + uint8_t dataCommRate; + uint8_t vectorCommRate; + uint8_t summaryCommRate; + dip_estimate_t* allEsts; + dip_index_t i; + + uint16_t E, D, L, V, C; + + allEsts = call DIPEstimates.getEstimates(); + highEst = 0; + dataCommRate = call DIPDataDecision.getCommRate(); + vectorCommRate = call DIPVectorDecision.getCommRate(); + summaryCommRate = call DIPSummaryDecision.getCommRate(); + + if(dataCommRate > 1) { + dbg("DIPLogicP", "Heard data\n"); + return ID_DIP_INVALID; + } + + // if there is an estimate with highest estimate value, send + for(i = 0; i < UQCOUNT_DIP; i++) { + est = allEsts[i]; + if(est >= DIP_DATA_ESTIMATE) { return ID_DIP_DATA; } + if(est > highEst) { highEst = est; }; + } + + // didn't send or hear data at this point + if(vectorCommRate + summaryCommRate > 1) { + dbg("DIPLogicP", "Heard an advertisement\n"); + return ID_DIP_INVALID; + } + + // corner case, if hash is too short + if(call DIPEstimates.estimateToHashlength(highEst) <= DIP_VECTOR_VALUES_PER_PACKET) { + return ID_DIP_VECTOR; + } + + // now we make the DIP decision + C = dataCommRate + vectorCommRate + summaryCommRate; + if(C == 0) C = 1; // don't want to divide by zero + E = highEst; + D = DIP_DATA_ESTIMATE; + L = call DIPEstimates.estimateToHashlength(E); + V = DIP_VECTOR_VALUES_PER_PACKET; + + dbg("DIPLogicP", "D=%u, E=%u, L=%u, V=%u, C=%u\n", D, E, L, V, C); + if((D - E) < (L / (C * V))) { + return ID_DIP_SUMMARY; + } + return ID_DIP_VECTOR; + } + +} diff --git a/tos/lib/net/dip/DIPSummaryC.nc b/tos/lib/net/dip/DIPSummaryC.nc new file mode 100644 index 00000000..cb1d1770 --- /dev/null +++ b/tos/lib/net/dip/DIPSummaryC.nc @@ -0,0 +1,22 @@ + +configuration DIPSummaryC { + provides interface DIPDecision; + + uses interface DIPSend as SummarySend; + uses interface DIPReceive as SummaryReceive; + + uses interface DIPHelp; + uses interface DIPEstimates; +} + +implementation { + components DIPSummaryP; + DIPDecision = DIPSummaryP; + SummarySend = DIPSummaryP; + SummaryReceive = DIPSummaryP; + DIPHelp = DIPSummaryP; + DIPEstimates = DIPSummaryP; + + components RandomC; + DIPSummaryP.Random -> RandomC; +} diff --git a/tos/lib/net/dip/DIPSummaryP.nc b/tos/lib/net/dip/DIPSummaryP.nc new file mode 100644 index 00000000..7b49e305 --- /dev/null +++ b/tos/lib/net/dip/DIPSummaryP.nc @@ -0,0 +1,271 @@ + +// Need to deal with non powers of base for the length of the hash + +#include + +module DIPSummaryP { + provides interface DIPDecision; + + uses interface DIPSend as SummarySend; + uses interface DIPReceive as SummaryReceive; + + uses interface DIPHelp; + uses interface DIPEstimates; + + uses interface Random; +} + +implementation { + void findRangeShadow(dip_index_t* left, dip_index_t *right); + uint32_t buildRange(dip_index_t left, dip_index_t right); + uint32_t computeHash(dip_index_t left, dip_index_t right, + dip_version_t* basedata, uint32_t salt); + uint32_t computeBloomHash(dip_index_t left, dip_index_t right, + dip_version_t* basedata, uint32_t salt); + void splitRange(uint32_t info, dip_index_t* left, dip_index_t* right); + void adjustEstimatesSame(dip_index_t left, dip_index_t right); + void adjustEstimatesDiff(dip_index_t left, dip_index_t rightt, + dip_version_t* data, uint32_t salt, + uint32_t bHash); + + uint8_t commRate; + // this can be combined with pairs_t in DIPVectorP maybe? + dip_estimate_t shadowEstimates[UQCOUNT_DIP]; + + command uint8_t DIPDecision.getCommRate() { + return commRate; + } + + command void DIPDecision.resetCommRate() { + commRate = 0; + } + + command error_t DIPDecision.send() { + dip_index_t i, j, left, right; + dip_version_t* allVers; + dip_estimate_t* allEsts; + uint32_t salt; + + dip_msg_t* dmsg; + dip_summary_msg_t* dsmsg; + + dmsg = (dip_msg_t*) call SummarySend.getPayloadPtr(); + dmsg->type = ID_DIP_SUMMARY; + dsmsg = (dip_summary_msg_t*) dmsg->content; + + allVers = call DIPHelp.getAllVersions(); + allEsts = call DIPEstimates.getEstimates(); + salt = call Random.rand32(); + + for(i = 0; i < UQCOUNT_DIP; i++) { + shadowEstimates[i] = allEsts[i]; + } + + for(i = 0; i < DIP_SUMMARY_ENTRIES_PER_PACKET; i += 3) { + findRangeShadow(&left, &right); + dbg("DIPSummaryP", "Found range %u, %u\n", left, right); + dsmsg->info[i] = buildRange(left, right); + dsmsg->info[i+1] = computeHash(left, right, allVers, salt); + dsmsg->info[i+2] = computeBloomHash(left, right, allVers, salt); + for(j = left; j < right; j++) { + shadowEstimates[j] = 0; + } + dbg("DIPSummaryP", "Hash Entry: %08x %08x %08x\n", + dsmsg->info[i], dsmsg->info[i+1], dsmsg->info[i+2]); + } + + dsmsg->unitLen = DIP_SUMMARY_ENTRIES_PER_PACKET; + dsmsg->salt = salt; + + for(i = 0; i < DIP_SUMMARY_ENTRIES_PER_PACKET; i += 3) { + splitRange(dsmsg->info[i], &left, &right); + adjustEstimatesSame(left, right); + } + + return call SummarySend.send(sizeof(dip_msg_t) + + sizeof(dip_summary_msg_t) + + (sizeof(uint32_t) * DIP_SUMMARY_ENTRIES_PER_PACKET)); + } + + event void SummaryReceive.receive(void* payload, uint8_t len) { + dip_summary_msg_t* dsmsg; + uint8_t unitlen; + uint32_t salt, myHash; + uint8_t i; + dip_index_t left, right; + dip_version_t* allVers; + + commRate = commRate + 1; + + dsmsg = (dip_summary_msg_t*) payload; + unitlen = dsmsg->unitLen; + salt = dsmsg->salt; + allVers = call DIPHelp.getAllVersions(); + + for(i = 0; i < unitlen; i += 3) { + splitRange(dsmsg->info[i], &left, &right); + myHash = computeHash(left, right, allVers, salt); + if(myHash != dsmsg->info[i+1]) { + // hashes don't match + adjustEstimatesDiff(left, right, allVers, salt, dsmsg->info[i+2]); + } + else { + // hashes match + adjustEstimatesSame(left, right); + } + } + + } + + void findRangeShadow(dip_index_t* left, dip_index_t *right) { + dip_estimate_t est1; + dip_estimate_t est2; + dip_hashlen_t len; + dip_index_t highIndex; + dip_index_t i; + dip_index_t LBound; + dip_index_t RBound; + uint16_t runEstSum; + uint16_t highEstSum; + + // find highest estimate + // initialize test + highIndex = 0; + est1 = shadowEstimates[0]; + + // Get the highest estimate key + for(i = 0; i < UQCOUNT_DIP; i++) { + est2 = shadowEstimates[i]; + if(est2 > est1) { + highIndex = i; + est1 = est2; + } + } + len = call DIPEstimates.estimateToHashlength(est1); + dbg("DIPSummaryP","Highest key at %u with estimate %u and thus len %u\n", + highIndex, est1, len); + + // initialize bounds on range + if(highIndex < len - 1) { LBound = 0; } + else { LBound = highIndex - len + 1; } + if(LBound + len > UQCOUNT_DIP) { RBound = UQCOUNT_DIP; } + else { RBound = highIndex + len; } + + // adjust length if necessary + if(RBound - LBound < len) { len = RBound - LBound; } + + // initialize first range + highEstSum = 0; + highIndex = LBound; + for(i = LBound; i < LBound + len; i++) { + est1 = shadowEstimates[i]; + highEstSum += est1; + } + dbg("DIPSummaryP", "First range: %u, %u = %u\n", LBound, LBound + len, + highEstSum); + + // iterate through the range + runEstSum = highEstSum; + dbg("DIPSummaryP", "Iterating from %u to %u\n", LBound, RBound); + for(i = LBound ; i + len <= RBound; i++) { + est1 = shadowEstimates[i]; + est2 = shadowEstimates[i + len]; + runEstSum = runEstSum - est1 + est2; + // dbg("Dissemination","Next sum: %u\n", runEstSum); + if(runEstSum > highEstSum) { + highEstSum = runEstSum; + highIndex = i + 1; + dbg("DIPSummaryP", "Next range: %u, %u = %u\n", highIndex, + highIndex + len, highEstSum); + } + } + + // and finish + *left = highIndex; + *right = highIndex + len; + } + + uint32_t buildRange(dip_index_t left, dip_index_t right) { + uint32_t range; + + range = ((uint32_t) left << 16) | right; + return range; + } + + uint32_t computeHash(dip_index_t left, dip_index_t right, + dip_version_t* basedata, uint32_t salt) { + dip_index_t i; + uint32_t hashValue = salt; + uint8_t *sequence; + + if(right <= left) return 0; + sequence = ((uint8_t*) (basedata + left)); + + for(i = 0; i <= (right-left-1)*sizeof(dip_version_t); i++) { + hashValue += sequence[i]; + hashValue += (hashValue << 10); + hashValue ^= (hashValue >> 6); + } + hashValue += (hashValue << 3); + hashValue ^= (hashValue >> 11); + hashValue += (hashValue << 15); + return hashValue; + } + + uint32_t computeBloomHash(dip_index_t left, dip_index_t right, + dip_version_t* basedata, uint32_t salt) { + dip_index_t i; + uint32_t bit; + uint32_t returnHash; + uint32_t indexSeqPair[2]; + + returnHash = 0; + for(i = left; i < right; i++) { + indexSeqPair[0] = i; + indexSeqPair[1] = basedata[i]; + bit = computeHash(0, 2, indexSeqPair, salt) % 32; + returnHash |= (1 << bit); + } + return returnHash; + } + + void splitRange(uint32_t info, dip_index_t* left, dip_index_t* right) { + *right = info & 0xFFFF; + *left = (info >> 16) & 0xFFFF; + } + + void adjustEstimatesSame(dip_index_t left, dip_index_t right) { + dip_index_t i; + + for(i = left; i < right; i++) { + call DIPEstimates.decEstimateByIndex(i); + } + } + + void adjustEstimatesDiff(dip_index_t left, dip_index_t right, + dip_version_t* data, uint32_t salt, + uint32_t bHash) { + dip_index_t i; + dip_estimate_t est; + dip_key_t key; + uint32_t indexSeqPair[2]; + uint32_t bit; + + est = call DIPEstimates.hashlengthToEstimate(right - left) + 1; // + 1 to improve search + for(i = left; i < right; i++) { + indexSeqPair[0] = i; + indexSeqPair[1] = data[i]; + bit = computeHash(0, 2, indexSeqPair, salt) % 32; + key = call DIPHelp.indexToKey(i); + if(bHash & (1 << bit)) { + //set estimate only if better + call DIPEstimates.setSummaryEstimateByIndex(i, est); + } + else { + dbg("DisseminationDebug", "Key %x definitely different\n", key); + call DIPEstimates.setVectorEstimate(key); + } + } + } + +} diff --git a/tos/lib/net/dip/DIPTrickleMilliC.nc b/tos/lib/net/dip/DIPTrickleMilliC.nc new file mode 100644 index 00000000..197e271a --- /dev/null +++ b/tos/lib/net/dip/DIPTrickleMilliC.nc @@ -0,0 +1,62 @@ +// $Id$ +/* + * "Copyright (c) 2006 Stanford University. All rights reserved. + * + * Permission to use, copy, modify, and distribute this software and + * its documentation for any purpose, without fee, and without written + * agreement is hereby granted, provided that the above copyright + * notice, the following two paragraphs and the author appear in all + * copies of this software. + * + * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES + * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN + * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + * + * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE + * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY + * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, + * ENHANCEMENTS, OR MODIFICATIONS." + */ + +/* + * Configuration that encapsulates the trickle timer implementation to + * its needed services and initialization. For details on the working + * of the parameters, please refer to Levis et al., "A Self-Regulating + * Algorithm for Code Maintenance and Propagation in Wireless Sensor + * Networks," NSDI 2004. + * + * @param l Lower bound of the time period in seconds. + * @param h Upper bound of the time period in seconds. + * @param k Redundancy constant. + * @param count How many timers to provide. + * + * @author Philip Levis + * @author Gilman Tolle + * @date Jan 7 2006 + */ + + +configuration DIPTrickleMilliC { + provides interface DIPTrickleTimer as TrickleTimer; +} +implementation { + components DIPTrickleMilliP as TrickleP; + components MainC, RandomC; + components new TimerMilliC() as PeriodicIntervalTimer; + components new TimerMilliC() as SingleEventTimer; + components LedsC; + TrickleTimer = TrickleP; + + TrickleP.PeriodicIntervalTimer -> PeriodicIntervalTimer; + TrickleP.SingleEventTimer -> SingleEventTimer; + TrickleP.Random -> RandomC; + + TrickleP.Leds -> LedsC; + MainC.SoftwareInit -> TrickleP; +} + + diff --git a/tos/lib/net/dip/DIPTrickleMilliP.nc b/tos/lib/net/dip/DIPTrickleMilliP.nc new file mode 100644 index 00000000..99ca4ecb --- /dev/null +++ b/tos/lib/net/dip/DIPTrickleMilliP.nc @@ -0,0 +1,120 @@ +// $Id$ +/* + * "Copyright (c) 2006 Stanford University. All rights reserved. + * + * Permission to use, copy, modify, and distribute this software and + * its documentation for any purpose, without fee, and without written + * agreement is hereby granted, provided that the above copyright + * notice, the following two paragraphs and the author appear in all + * copies of this software. + * + * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES + * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN + * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + * + * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE + * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY + * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, + * ENHANCEMENTS, OR MODIFICATIONS." + */ + +/* + * Module that provides a service instance of trickle timers. For + * details on the working of the parameters, please refer to Levis et + * al., "A Self-Regulating Algorithm for Code Maintenance and + * Propagation in Wireless Sensor Networks," NSDI 2004. + * + * @param l Lower bound of the time period in seconds. + * @param h Upper bound of the time period in seconds. + * @param k Redundancy constant. + * @param count How many timers to provide. + * + * @author Philip Levis + * @author Gilman Tolle + * @date Jan 7 2006 + */ + +#include +#include + +module DIPTrickleMilliP { + provides { + interface Init; + interface DIPTrickleTimer as TrickleTimer; + } + uses { + interface Timer as PeriodicIntervalTimer; + interface Timer as SingleEventTimer; + interface Random; + interface Leds; + } +} +implementation { + + uint32_t period; + + command error_t Init.init() { + period = DIP_TAU_HIGH; + return SUCCESS; + } + + /** + * Start a trickle timer. Reset the counter to 0. + */ + command error_t TrickleTimer.start() { + call PeriodicIntervalTimer.startOneShot(period); + dbg("DIPTrickleMilliP", + "Starting trickle timer @ %s\n", sim_time_string()); + return SUCCESS; + } + + /** + * Stop the trickle timer. This call sets the timer period to H. + */ + command void TrickleTimer.stop() { + call PeriodicIntervalTimer.stop(); + dbg("DIPTrickleMilliP", + "Stopping trickle timer @ %s\n", sim_time_string()); + } + + /** + * Reset the timer period to L. If called while the timer is running, + * then a new interval (of length L) begins immediately. + */ + command void TrickleTimer.reset() { + period = DIP_TAU_LOW; + call PeriodicIntervalTimer.stop(); + call PeriodicIntervalTimer.startOneShot(period); + dbg("DIPTrickleMilliP", + "Resetting trickle timer @ %s\n", sim_time_string()); + } + + command void TrickleTimer.maxInterval() { + period = DIP_TAU_HIGH; + } + + /** + * The trickle timer has fired. Signaled if C > K. + */ + event void PeriodicIntervalTimer.fired() { + uint32_t dtfire; + + dtfire = (call Random.rand16() % (period / 2)) + (period / 2); + dbg("DIPTrickleMilliP", "Scheduling Trickle event with %u\n", dtfire); + call SingleEventTimer.startOneShot(dtfire); + period = signal TrickleTimer.requestWindowSize(); + call PeriodicIntervalTimer.startOneShot(period); + //call Leds.led0Toggle(); + } + + event void SingleEventTimer.fired() { + dbg("Trickle", "Firing Trickle Event Timer\n"); + signal TrickleTimer.fired(); + } +} + + diff --git a/tos/lib/net/dip/DIPVectorC.nc b/tos/lib/net/dip/DIPVectorC.nc new file mode 100644 index 00000000..14d79f7a --- /dev/null +++ b/tos/lib/net/dip/DIPVectorC.nc @@ -0,0 +1,23 @@ + +configuration DIPVectorC { + provides interface DIPDecision; + + uses interface DIPSend as VectorSend; + uses interface DIPReceive as VectorReceive; + + uses interface DIPHelp; + uses interface DIPEstimates; +} + +implementation { + components DIPVectorP; + DIPDecision = DIPVectorP; + VectorSend = DIPVectorP; + VectorReceive = DIPVectorP; + DIPHelp = DIPVectorP; + DIPEstimates = DIPVectorP; + + components RandomC; + DIPVectorP.Random -> RandomC; + +} diff --git a/tos/lib/net/dip/DIPVectorP.nc b/tos/lib/net/dip/DIPVectorP.nc new file mode 100644 index 00000000..4f775174 --- /dev/null +++ b/tos/lib/net/dip/DIPVectorP.nc @@ -0,0 +1,142 @@ + +#include + +module DIPVectorP { + provides interface DIPDecision; + + uses interface DIPSend as VectorSend; + uses interface DIPReceive as VectorReceive; + + uses interface DIPHelp; + uses interface DIPEstimates; + + uses interface Random; +} + +implementation { + uint8_t commRate = 0; + typedef struct pairs_t { + dip_estimate_t estimate; + dip_key_t key; + } pairs_t; + pairs_t pairs[UQCOUNT_DIP]; // This is large memory footprint + + int myComparator(const void* a, const void* b); + void randomizeRun(pairs_t* localPairs, dip_index_t length); + + command uint8_t DIPDecision.getCommRate() { + return commRate; + } + + command void DIPDecision.resetCommRate() { + commRate = 0; + } + + command error_t DIPDecision.send() { + dip_index_t i, j, r; + dip_key_t sendkey; + dip_estimate_t* ests; + + dip_msg_t* dmsg; + dip_vector_msg_t* dvmsg; + + dmsg = call VectorSend.getPayloadPtr(); + if(dmsg == NULL) { + return FAIL; + } + + ests = call DIPEstimates.getEstimates(); + // get all estimates and sort + for(i = 0; i < UQCOUNT_DIP; i++) { + pairs[i].key = call DIPHelp.indexToKey(i); + pairs[i].estimate = ests[i]; + } + qsort(pairs, UQCOUNT_DIP, sizeof(pairs_t), myComparator); + j = pairs[0].estimate; + r = 0; + for(i = 0; i < UQCOUNT_DIP; i++) { + if(pairs[i].estimate < j) { + randomizeRun(&pairs[r], i - r); + j = pairs[i].estimate; + r = i; + } + } + // randomize the last set + randomizeRun(&pairs[r], UQCOUNT_DIP - r); + + // fill up the packet + dmsg->type = ID_DIP_VECTOR; + dvmsg = (dip_vector_msg_t*) dmsg->content; + dvmsg->unitLen = DIP_VECTOR_ENTRIES_PER_PACKET; + for(i = 0, j = 0; + i < DIP_VECTOR_ENTRIES_PER_PACKET; + i += 2, j++) { + sendkey = pairs[j].key; + dvmsg->vector[i] = sendkey; + dvmsg->vector[i+1] = call DIPHelp.keyToVersion(sendkey); + // adjust estimate + call DIPEstimates.decEstimateByKey(sendkey); + } + + return call VectorSend.send(sizeof(dip_msg_t) + sizeof(dip_vector_msg_t) + + (DIP_VECTOR_ENTRIES_PER_PACKET * sizeof(uint32_t))); + } + + event void VectorReceive.receive(void* payload, uint8_t len) { + dip_vector_msg_t* dvmsg; + uint8_t unitlen; + + uint8_t i; + dip_key_t vectorkey; + dip_version_t vectorver; + dip_version_t myver; + + commRate = commRate + 1; + dvmsg = (dip_vector_msg_t*) payload; + unitlen = dvmsg->unitLen; + + for(i = 0; i < unitlen; i += 2) { + vectorkey = dvmsg->vector[i]; + vectorver = dvmsg->vector[i+1]; + myver = call DIPHelp.keyToVersion(vectorkey); + + // TODO: handle the invalid versions + if(myver < vectorver) { + call DIPEstimates.setVectorEstimate(vectorkey); + } + else if(myver > vectorver) { + call DIPEstimates.setDataEstimate(vectorkey); + } + else if(myver == vectorver) { + call DIPEstimates.decEstimateByKey(vectorkey); + } + } + + } + + int myComparator(const void* a, const void* b) { + const pairs_t *x = (const pairs_t *) a; + const pairs_t *y = (const pairs_t *) b; + if( x->estimate < y->estimate ) { return 1; } + if( x->estimate > y->estimate ) { return -1; } + return 0; + } + + void randomizeRun(pairs_t* localPairs, dip_index_t length) { + dip_index_t i,j; + dip_index_t rLength = length; + pairs_t temp; + + // don't move the last one + for(i = 0; i < length - 1; i++, rLength--) { + j = i + (call Random.rand16() % rLength); + temp.key = localPairs[i].key; + temp.estimate = localPairs[i].estimate; + localPairs[i].key = localPairs[j].key; + localPairs[i].estimate = localPairs[j].estimate; + localPairs[j].key = temp.key; + localPairs[j].estimate = temp.estimate; + } + } + +} diff --git a/tos/lib/net/dip/DIPVersionC.nc b/tos/lib/net/dip/DIPVersionC.nc new file mode 100644 index 00000000..fbf3c94e --- /dev/null +++ b/tos/lib/net/dip/DIPVersionC.nc @@ -0,0 +1,14 @@ + +#include + +configuration DIPVersionC { + provides interface DIPHelp; + + provides interface DisseminationUpdate[dip_key_t key]; +} + +implementation { + components DIPVersionP; + DIPHelp = DIPVersionP; + DisseminationUpdate = DIPVersionP; +} diff --git a/tos/lib/net/dip/DIPVersionP.nc b/tos/lib/net/dip/DIPVersionP.nc new file mode 100644 index 00000000..9c2afefa --- /dev/null +++ b/tos/lib/net/dip/DIPVersionP.nc @@ -0,0 +1,107 @@ + +module DIPVersionP { + provides interface DIPHelp; + + provides interface DisseminationUpdate[dip_key_t key]; +} + +implementation { + int lessThan(const void* a, const void* b); + + // keys are ordered from smallest to largest. + dip_key_t keys[UQCOUNT_DIP]; + dip_version_t versions[UQCOUNT_DIP]; + dip_index_t count = 0; + + command void DIPHelp.registerKey(dip_key_t key) { + dip_index_t i; + + keys[count] = key; + count = count + 1; + if(count == UQCOUNT_DIP) { + qsort(keys, UQCOUNT_DIP, sizeof(dip_key_t), lessThan); + dbg("DIPVersionP","Key registration complete!\n"); + for(i = 0; i < UQCOUNT_DIP; i++) { + dbg("DIPVersionP","Key %x\n", keys[i]); + } + } + } + + command void DisseminationUpdate.change[dip_key_t key](dip_data_t* val) { + dip_index_t i; + dip_version_t ver; + + i = call DIPHelp.keyToIndex(key); + ver = versions[i]; + + // the version has node ID embedded in it, so need to do some shifts + ver = ver >> 16; + ver++; + if ( ver == DIP_UNKNOWN_VERSION ) { ver++; } + ver = ver << 16; + ver += TOS_NODE_ID; + + versions[i] = ver; + } + + command dip_index_t DIPHelp.keyToIndex(dip_key_t key) { + dip_index_t answer; + dip_index_t i; + + answer = DIP_UNKNOWN_INDEX; + // linear search for now since it's easier + for(i = 0; i < UQCOUNT_DIP; i++) { + if(keys[i] == key) { + answer = i; + break; + } + } + dbg("DIPVersionP", "Converting key %x to index %u\n", key, answer); + return answer; + } + + command dip_key_t DIPHelp.indexToKey(dip_index_t ind) { + return keys[ind]; + } + + command dip_version_t DIPHelp.keyToVersion(dip_key_t key) { + dip_index_t i; + + i = call DIPHelp.keyToIndex(key); + return versions[i]; + } + + command void DIPHelp.setVersion(dip_key_t key, dip_version_t ver) { + dip_index_t i; + + i = call DIPHelp.keyToIndex(key); + versions[i] = ver; + dbg("DIPVersionP","Setting key %x at index %u to version %x\n", key, i, ver); + } + + command dip_version_t* DIPHelp.getAllVersions() { + return versions; + } + + int lessThan(const void* a, const void* b) { + if ((*(dip_key_t*) a) < (*(dip_key_t*) b)) { + return -1; + } + else if ((*(dip_key_t*) a) > (*(dip_key_t*) b)) { + return 1; + } + return 0; + } + + // binary search code which may be unstable + /* + dip_index_t answer; + + search_result = (dip_key_t*) bsearch(&key, &keys, UQCOUNT_DIP, + sizeof(dip_key_t), lessThan); + if(search_result == NULL) { + return DIP_UNKNOWN_INDEX; + } + answer = search_result - keys; + */ +} diff --git a/tos/lib/net/dip/DisseminationC.nc b/tos/lib/net/dip/DisseminationC.nc new file mode 100644 index 00000000..438a3b3e --- /dev/null +++ b/tos/lib/net/dip/DisseminationC.nc @@ -0,0 +1,11 @@ + +#include + +configuration DisseminationC { + provides interface StdControl; +} + +implementation { + components DIPLogicC; + StdControl = DIPLogicC; +} diff --git a/tos/lib/net/dip/DisseminatorC.nc b/tos/lib/net/dip/DisseminatorC.nc new file mode 100644 index 00000000..5826f465 --- /dev/null +++ b/tos/lib/net/dip/DisseminatorC.nc @@ -0,0 +1,77 @@ +#include + +/* + * Copyright (c) 2006 Arch Rock Corporation + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the + * distribution. + * - Neither the name of the Arch Rock Corporation nor the names of + * its contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * ARCHED ROCK OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE + * + */ + +/** + * The DisseminatorC component holds and synchronizes a single value + * of a chosen type, and identifies that value by a chosen 16-bit key. + * Different nodes should use the same key for the same value. + * + * See TEP118 - Dissemination for details. + * + * @param t the type of the object that will be disseminated + * @param key the 16-bit identifier of the disseminated object + * + * @author Gilman Tolle + * @version $Revision$ $Date$ + */ + +generic configuration DisseminatorC(typedef t, dip_key_t key) { + provides interface DisseminationValue; + provides interface DisseminationUpdate; +} +implementation { + enum { + JUST_NEED_COUNT = UQ_DIP + }; + + components new DisseminatorP(t, key); + DisseminationValue = DisseminatorP.AppDisseminationValue; + DisseminationUpdate = DisseminatorP.AppDisseminationUpdate; + + components LedsC; + DisseminatorP.Leds -> LedsC; + + components DIPLogicC; + DisseminatorP.DIPDisseminationUpdate -> DIPLogicC.DisseminationUpdate[key]; + + components DIPVersionC; + DisseminatorP.DIPHelp -> DIPVersionC; + + components MainC; + MainC.SoftwareInit -> DisseminatorP; + + components DIPDataC; + DIPDataC.DisseminationUpdate[key] -> DisseminatorP.DataDisseminationUpdate; + DIPDataC.DisseminationValue[key] -> DisseminatorP.DataDisseminationValue; +} diff --git a/tos/lib/net/dip/DisseminatorP.nc b/tos/lib/net/dip/DisseminatorP.nc new file mode 100644 index 00000000..15ec04cd --- /dev/null +++ b/tos/lib/net/dip/DisseminatorP.nc @@ -0,0 +1,107 @@ +/* + * Copyright (c) 2006 Arch Rock Corporation + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the + * distribution. + * - Neither the name of the Arch Rock Corporation nor the names of + * its contributors may be used to endorse or promote products derived + * from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS + * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE + * ARCHED ROCK OR ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED + * OF THE POSSIBILITY OF SUCH DAMAGE + * + */ + +/** + * The DisseminatorP module holds and synchronizes a single value of a + * chosen type. + * + * See TEP118 - Dissemination for details. + * + * @param t the type of the object that will be disseminated + * + * @author Gilman Tolle + * @version $Revision$ $Date$ + */ + +generic module DisseminatorP(typedef t, dip_key_t key) { + provides interface DisseminationValue as AppDisseminationValue; + provides interface DisseminationUpdate as AppDisseminationUpdate; + provides interface DisseminationUpdate as DataDisseminationUpdate; + provides interface DisseminationValue as DataDisseminationValue; + + provides interface Init; + + uses interface DisseminationUpdate as DIPDisseminationUpdate; + uses interface DIPHelp; + + uses interface Leds; +} +implementation { + dip_data_t valueCache; + + task void signalNewData() { + signal AppDisseminationValue.changed(); + } + + command error_t Init.init() { + call DIPHelp.registerKey(key); + return SUCCESS; + } + + // A sequence number is 32 bits. The top 16 bits are an incrementing + // counter, while the bottom 16 bits are a unique node identifier. + // But versions aren't stored here. + + command const t* AppDisseminationValue.get() { + return (t*) &valueCache; + } + + command void AppDisseminationValue.set( const t* val ) { + memcpy( &valueCache, val, sizeof(t) ); + } + + command void AppDisseminationUpdate.change( t* newVal ) { + memcpy( &valueCache, newVal, sizeof(t) ); + /* Increment the counter and append the local node ID later. */ + /* DIPLogicC doesn't care what the data actually is, + it just wants the key, so we cast it recklessly */ + call DIPDisseminationUpdate.change((dip_data_t*)newVal); + } + + command const dip_data_t* DataDisseminationValue.get() { + return (dip_data_t*) &valueCache; + } + + command void DataDisseminationValue.set( const dip_data_t* val ) { } + + command void DataDisseminationUpdate.change( dip_data_t* newVal ) { + memcpy( &valueCache, newVal, sizeof(dip_data_t) ); + //post signalNewData(); + signal AppDisseminationValue.changed(); + } + + + default event void AppDisseminationValue.changed() { } + + default event void DataDisseminationValue.changed() { } + +} diff --git a/tos/lib/net/dip/README b/tos/lib/net/dip/README new file mode 100644 index 00000000..48ae6118 --- /dev/null +++ b/tos/lib/net/dip/README @@ -0,0 +1,27 @@ + +Title: DIP +Author: Kaisen Lin +------------------ + +DIP is a dissemination protocol for detecting and disseminating new +items in a network. It uses the same interfaces as Drip. + +Data disseminated under DIP cannot be larger than 16 bytes. It was not +designed for large data items, but rather for many small data items. + +Ties, like Drip, are handled with higher node IDs serving as +tiebreakers. + +Key 0 is reserved, do not use it. + +There is minimal error checking, don't try to intentionally break +it. (e.g. illegal keys, weird and wacky version numbers) + +Usage: +------ + +To use include the following in your Makefile: + +CFLAGS += -I$(TOSDIR)/lib/net +CFLAGS += -I$(TOSDIR)/lib/net/dip +CFLAGS += -I$(TOSDIR)/lib/net/dip/interfaces diff --git a/tos/lib/net/dip/interfaces/DIPDecision.nc b/tos/lib/net/dip/interfaces/DIPDecision.nc new file mode 100644 index 00000000..86f00913 --- /dev/null +++ b/tos/lib/net/dip/interfaces/DIPDecision.nc @@ -0,0 +1,6 @@ + +interface DIPDecision { + command uint8_t getCommRate(); + command void resetCommRate(); + command error_t send(); +} diff --git a/tos/lib/net/dip/interfaces/DIPEstimates.nc b/tos/lib/net/dip/interfaces/DIPEstimates.nc new file mode 100644 index 00000000..512c5bf0 --- /dev/null +++ b/tos/lib/net/dip/interfaces/DIPEstimates.nc @@ -0,0 +1,15 @@ + +#include + +interface DIPEstimates { + command dip_estimate_t* getEstimates(); + command void decEstimateByIndex(dip_index_t i); + command void decEstimateByKey(dip_key_t key); + command dip_hashlen_t estimateToHashlength(dip_estimate_t est); + command dip_estimate_t hashlengthToEstimate(dip_hashlen_t len); + // special event to reset trickle timer too + command void setDataEstimate(dip_key_t key); + command void setVectorEstimate(dip_key_t key); + command void setSummaryEstimateByIndex(dip_index_t ind, + dip_estimate_t est); +} diff --git a/tos/lib/net/dip/interfaces/DIPHelp.nc b/tos/lib/net/dip/interfaces/DIPHelp.nc new file mode 100644 index 00000000..7b812711 --- /dev/null +++ b/tos/lib/net/dip/interfaces/DIPHelp.nc @@ -0,0 +1,12 @@ + +#include + +interface DIPHelp { + command void registerKey(dip_key_t key); + + command dip_index_t keyToIndex(dip_key_t key); + command dip_key_t indexToKey(dip_index_t ind); + command dip_version_t keyToVersion(dip_key_t key); + command void setVersion(dip_key_t key, dip_version_t ver); + command dip_version_t* getAllVersions(); +} diff --git a/tos/lib/net/dip/interfaces/DIPReceive.nc b/tos/lib/net/dip/interfaces/DIPReceive.nc new file mode 100644 index 00000000..98f6b9b3 --- /dev/null +++ b/tos/lib/net/dip/interfaces/DIPReceive.nc @@ -0,0 +1,4 @@ + +interface DIPReceive { + event void receive(void* payload, uint8_t len); +} diff --git a/tos/lib/net/dip/interfaces/DIPSend.nc b/tos/lib/net/dip/interfaces/DIPSend.nc new file mode 100644 index 00000000..2ee59986 --- /dev/null +++ b/tos/lib/net/dip/interfaces/DIPSend.nc @@ -0,0 +1,6 @@ + +interface DIPSend { + command error_t send(uint8_t len); + command void* getPayloadPtr(); + command uint8_t maxPayloadLength(); +} diff --git a/tos/lib/net/dip/interfaces/DIPTrickleTimer.nc b/tos/lib/net/dip/interfaces/DIPTrickleTimer.nc new file mode 100644 index 00000000..30237602 --- /dev/null +++ b/tos/lib/net/dip/interfaces/DIPTrickleTimer.nc @@ -0,0 +1,88 @@ +// $Id$ +/* + * "Copyright (c) 2006 Stanford University. All rights reserved. + * + * Permission to use, copy, modify, and distribute this software and + * its documentation for any purpose, without fee, and without written + * agreement is hereby granted, provided that the above copyright + * notice, the following two paragraphs and the author appear in all + * copies of this software. + * + * IN NO EVENT SHALL STANFORD UNIVERSITY BE LIABLE TO ANY PARTY FOR + * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES + * ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN + * IF STANFORD UNIVERSITY HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH + * DAMAGE. + * + * STANFORD UNIVERSITY SPECIFICALLY DISCLAIMS ANY WARRANTIES, + * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF + * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE + * PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND STANFORD UNIVERSITY + * HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES, + * ENHANCEMENTS, OR MODIFICATIONS." + */ + +/* + * A network trickle timer. A trickle timer has a period in the range + * [L, H]. After firing, the period is doubled, up to H. If the period + * is P, then the timer is scheduled to fire in the interval [0.5P, P] + * (the second half of a period). The period can be reset to L (the + * smallest period, and therefore the highest frequency). + * + * The timer may be suppressed. If a user of the interface has heard + * enough packets from other nodes that indicate its transmitting a + * packet would be unncessarily redundant, then the timer does not + * fire. The timer has a constant K and a counter C. If C >e; K, then + * the timer does not fire. When an interval ends, C is reset to 0. + * Calling incrementCounter increments C by one. + * + * For details, refer to Levis et al., "A Self-Regulating Algorithm + * for Code Maintenance and Propagation in Wireless Sensor Networks," + * NSDI 2004. The component providing this interface defines the + * constants L, H, and K. + * + * @author Philip Levis + * @date Jan 7 2006 + */ + + +interface DIPTrickleTimer { + + /** + * Start the trickle timer. At boot, the timer period is its maximum + * value (H). If a protocol requires starting at the minimum value + * (e.g., fast start), then it should call reset before + * start. + * + * @return error_t SUCCESS if the timer was started, EBUSY if it is already + * running, and FAIL otherwise. + */ + command error_t start(); + + /** + * Stop the trickle timer. This call sets the timer period to H and + * C to 0. + */ + command void stop(); + + /** + * Reset the timer period to L. If called while the timer is + * running, then a new interval (of length L) begins immediately. + */ + command void reset(); + + /** + * The trickle timer has fired. Signaled if C > K. + */ + event void fired(); + + /** + * Compute the window size based on DIP's estimates + */ + event uint32_t requestWindowSize(); + + /** + * Resets the timer period to H. + */ + command void maxInterval(); +} diff --git a/tos/lib/net/dip/interfaces/DIPVersion.nc b/tos/lib/net/dip/interfaces/DIPVersion.nc new file mode 100644 index 00000000..80c4ceac --- /dev/null +++ b/tos/lib/net/dip/interfaces/DIPVersion.nc @@ -0,0 +1,7 @@ + +#include + +interface DIPVersion { + command void setVersion(); + command void incVersion(); +} \ No newline at end of file diff --git a/tos/lib/net/dip/qsort.c b/tos/lib/net/dip/qsort.c new file mode 100644 index 00000000..4b48e008 --- /dev/null +++ b/tos/lib/net/dip/qsort.c @@ -0,0 +1,151 @@ +/*- + * Copyright (c) 1992, 1993 + * The Regents of the University of California. All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. All advertising materials mentioning features or use of this software + * must display the following acknowledgement: + * This product includes software developed by the University of + * California, Berkeley and its contributors. + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ + +//#include + +typedef int cmp_t(const void *, const void *); +static char *med3(char *, char *, char *, cmp_t *); +static void swapfunc(char *, char *, int); + +#define min(a, b) ((a) < (b) ? (a) : (b)) + +/* + * Qsort routine from Bentley & McIlroy's "Engineering a Sort Function". + */ +#define swapcode(TYPE, parmi, parmj, n) { \ + int i = (n) / sizeof (TYPE); \ + register TYPE *pi = (TYPE *) (parmi); \ + register TYPE *pj = (TYPE *) (parmj); \ + do { \ + register TYPE t = *pi; \ + *pi++ = *pj; \ + *pj++ = t; \ + } while (--i > 0); \ +} + +static void +swapfunc(char *a, char* b, int n) +{ + swapcode(char, a, b, n) +} + +#define swap(a, b) swapfunc(a, b, es) + +#define vecswap(a, b, n) if ((n) > 0) swapfunc(a, b, n) + +static char * +med3(char* a, char* b, char* c, cmp_t* cmp) +{ + return cmp(a, b) < 0 ? + (cmp(b, c) < 0 ? b : (cmp(a, c) < 0 ? c : a )) + :(cmp(b, c) > 0 ? b : (cmp(a, c) < 0 ? a : c )); +} + +void +qsort(void* a, size_t n, size_t es, cmp_t* cmp) +{ + char *pa, *pb, *pc, *pd, *pl, *pm, *pn; + int d, r, swap_cnt; + +loop: + swap_cnt = 0; + if (n < 7) { + for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + pm = (char *)a + (n / 2) * es; + if (n > 7) { + pl = a; + pn = (char *)a + (n - 1) * es; + if (n > 40) { + d = (n / 8) * es; + pl = med3(pl, pl + d, pl + 2 * d, cmp); + pm = med3(pm - d, pm, pm + d, cmp); + pn = med3(pn - 2 * d, pn - d, pn, cmp); + } + pm = med3(pl, pm, pn, cmp); + } + swap(a, pm); + pa = pb = (char *)a + es; + + pc = pd = (char *)a + (n - 1) * es; + for (;;) { + while (pb <= pc && (r = cmp(pb, a)) <= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pa, pb); + pa += es; + } + pb += es; + } + while (pb <= pc && (r = cmp(pc, a)) >= 0) { + if (r == 0) { + swap_cnt = 1; + swap(pc, pd); + pd -= es; + } + pc -= es; + } + if (pb > pc) + break; + swap(pb, pc); + swap_cnt = 1; + pb += es; + pc -= es; + } + if (swap_cnt == 0) { /* Switch to insertion sort */ + for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es) + for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; + pl -= es) + swap(pl, pl - es); + return; + } + + pn = (char *)a + n * es; + r = min(pa - (char *)a, pb - pa); + vecswap(a, pb - r, r); + r = min(pd - pc, pn - pd - es); + vecswap(pb, pn - r, r); + if ((r = pb - pa) > es) + qsort(a, r / es, es, cmp); + if ((r = pd - pc) > es) { + /* Iterate rather than recurse to save stack space */ + a = pn - r; + n = r / es; + goto loop; + } +/* qsort(pn - r, r / es, es, cmp);*/ +} -- 2.39.2