Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
hit_sig.c
Go to the documentation of this file.
1 
13 /*
14  * <license>
15  *
16  * Hitmap v1.2
17  *
18  * This software is provided to enhance knowledge and encourage progress in the scientific
19  * community. It should be used only for research and educational purposes. Any reproduction
20  * or use for commercial purpose, public redistribution, in source or binary forms, with or
21  * without modifications, is NOT ALLOWED without the previous authorization of the copyright
22  * holder. The origin of this software must not be misrepresented; you must not claim that you
23  * wrote the original software. If you use this software for any purpose (e.g. publication),
24  * a reference to the software package and the authors must be included.
25  *
26  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS "AS IS" AND ANY
27  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
28  * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
29  * THE AUTHORS OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
30  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
33  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
34  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
35  *
36  * Copyright (c) 2007-2015, Trasgo Group, Universidad de Valladolid.
37  * All rights reserved.
38  *
39  * More information on http://trasgo.infor.uva.es/
40  *
41  * </license>
42 */
43 
44 #include <stdio.h>
45 #include <hit_sig.h>
46 
47 /* Hit SIGNATURE NULL CONSTANT */
48 HitSig HIT_SIG_NULL = HIT_SIG_NULL_STATIC;
49 HitSig HIT_SIG_WHOLE = HIT_SIG_WHOLE_STATIC;
50 
51 
52 
53 /* Hitmap INTERNAL HELPER:
54  * COMPUTE THE G.C.D. OF TWO INTEGERS WITH THE EXTENDED EUCLIDEAN METHOD
55  * RETURNS THE GCD AND THE TWO REMAINDERS
56  */
57 void hit_utilExtendedEuclideanGCD( int a, int b, int *gcd, int *pLastx, int *pLasty ) {
58  int x=0, lastx=1;
59  int y=1, lasty=0;
60 
61  while ( b != 0 ) {
62  int quotient = a / b;
63 
64  int temp=b;
65  b = a % b;
66  a = temp;
67 
68  temp = x;
69  x = lastx-quotient*x;
70  lastx = temp;
71 
72  temp = y;
73  y = lasty-quotient*y;
74  lasty = temp;
75  }
76 
77  *gcd = a;
78  *pLastx = lastx;
79  *pLasty = lasty;
80 }
81 
82 
87  HitSig res = HIT_SIG_NULL;
88 
89  /* 0. REJECT TRIVIAL NON-OVERLAPPING RANGES */
90  if ( s1.end < s2.begin || s2.end < s1.begin ) return HIT_SIG_NULL;
91 
92  /* 1. SIMPLER PROCEDURE FOR SIGNATURES WITH STRIDE 1 */
93  if ( s1.stride == 1 && s2.stride == 1 ) {
94  /* 1.1. GET MAXIMUM OF BEGINS AND MINIMUM OF ENDS */
95  res.begin = (s1.begin > s2.begin) ? s1.begin : s2.begin;
96  res.end = (s1.end < s2.end) ? s1.end : s2.end;
97  res.stride = 1;
98  }
99  /* 2. PROCEDURE FOR ONLY ONE SIGNATURE WITH STRIDE 1 */
100  else if ( s1.stride == 1 || s2.stride == 1) {
101  /* 2.1. IDENTIFY THE STRIDED SIGNATURE AND THE NO-STRIDED SIGNATURE */
102  HitSig stridedSig, noStridedSig;
103  if ( s1.stride != 1 ) { stridedSig = s1; noStridedSig = s2; }
104  else { stridedSig = s2; noStridedSig = s1; }
105 
106  /* 2.2. BEGIN */
107  if ( noStridedSig.begin <= stridedSig.begin ) res.begin = stridedSig.begin;
108  else {
109  int displacement = (noStridedSig.begin - stridedSig.begin) % stridedSig.stride;
110  if ( displacement == 0 ) res.begin = noStridedSig.begin;
111  else res.begin = noStridedSig.begin - displacement + stridedSig.stride;
112  }
113 
114  /* 2.3. END */
115  if ( noStridedSig.end >= stridedSig.end ) res.end = stridedSig.end;
116  else res.end = noStridedSig.end;
117 
118  /* 2.4. CHECK NO INTERSECTION CONDITION */
119  if ( res.begin > res.end ) return HIT_SIG_NULL;
120 
121  /* 2.4. NORMALIZE END AND COPY STRIDE */
122  res.end = res.end - ( res.end - res.begin ) % stridedSig.stride;
123  res.stride = stridedSig.stride;
124  }
125  /* 3. GENERAL PROCEDURE FOR STRIDED SIGNATURES */
126  else {
127  /* 3.2. SORT SIGNATURES BY STRIDE */
128  HitSig low, high;
129  if ( s1.stride <= s2.stride ) { low = s1; high = s2; }
130  else { low = s2; high = s1; }
131 
132  /* 3.3. DISPLACE SIGNATURES: HIGH STRIDED SIGNATURE WILL BEGIN AT 0 */
133  int displacement = high.begin;
134  high.begin = 0;
135  high.end = high.end - displacement;
136  low.begin = low.begin - displacement;
137  low.end = low.end - displacement;
138 
139  int lowerEnd = ( low.end < high.end ) ? low.end : high.end;
140  int higherBegin = ( low.begin > high.begin ) ? low.begin : high.begin;
141 
142  /* 3.4. OBTAIN THE SMALLER POSITIVE POINT OF THE LOW STRIDED SIGNATURE: norm */
143  int norm = low.begin % low.stride;
144  if ( norm < 0 ) norm = norm + low.stride;
145 
146  /* 3.5. COMPUTE G.C.D. AND L.C.M. OF STRIDES */
147  int gcd, lastx, lasty;
148  hit_utilExtendedEuclideanGCD( high.stride, low.stride, &gcd, &lastx, &lasty );
149  int lcm = high.stride / gcd * low.stride;
150 
151  /* 3.6. PARTICULAR CASE: norm == 0, TRIVIAL COINCIDENCE */
152  if ( norm == 0 ) {
153  /* 3.6.1. GET NEW BEGIN */
154  if ( low.begin <= 0 ) res.begin = 0;
155  else if ( low.begin % lcm == 0 ) res.begin = low.begin;
156  else res.begin = low.begin + lcm - low.begin % lcm;
157  }
158  /* 3.7. GENERAL CASE: norm != 0 */
159  else {
160  /* 3.7.1. CHECK BASIC INTERSECTION CONDITION */
161  if ( norm % gcd != 0 ) return HIT_SIG_NULL;
162 
163  /* 3.7.2. OBTAIN FIRST COINCIDENCE */
164  int multLowStride;
165  int jumps = norm / gcd;
166  int cycle = high.stride / gcd;
167 
168  if ( lasty < 0 ) multLowStride = jumps * -lasty % cycle;
169  else multLowStride = cycle - ( jumps * lasty % cycle );
170 
171  int coincidence = norm + multLowStride * low.stride;
172 
173  /* 3.7.3. COMPUTE RESULT BEGIN */
174  if ( coincidence >= higherBegin ) res.begin = coincidence;
175  else {
176  int adjust = ( higherBegin - coincidence ) % lcm;
177  if ( adjust == 0 ) res.begin = higherBegin;
178  else res.begin = higherBegin + lcm - adjust;
179  }
180  }
181 
182  /* 3.8. CHECK LAST INTERSECTION CONDITION */
183  if ( res.begin > lowerEnd ) return HIT_SIG_NULL;
184 
185  /* 3.9. FILL UP RESULT WITH STRIDE AND NORMALIZED END */
186  res.stride = lcm;
187  res.end = lowerEnd - ( lowerEnd - res.begin ) % lcm;
188 
189  /* 3.10. RESTORE DISPLACEMENT */
190  res.begin += displacement;
191  res.end += displacement;
192  }
193 
194  /* 4. RETURN INTERSECTION */
195  return res;
196 }
197 
198 
#define norm(vv)
#define y(a, b, c)
Definition: hit_sig.h:79
HitSig hit_sigIntersect(HitSig s1, HitSig s2)
Definition: hit_sig.c:86
int begin
Definition: hit_sig.h:80
HitSig HIT_SIG_NULL
Definition: hit_sig.c:48
#define x
int end
Definition: hit_sig.h:81
HitSig HIT_SIG_WHOLE
Definition: hit_sig.c:49
int stride
Definition: hit_sig.h:82
void hit_utilExtendedEuclideanGCD(int a, int b, int *gcd, int *pLastx, int *pLasty)
Definition: hit_sig.c:57