source: vis_dev/vis-2.3/src/img/imgTfmCache.c @ 17

Last change on this file since 17 was 14, checked in by cecile, 13 years ago

vis2.3
File size: 31.3 KB
Line 
1/**CFile***********************************************************************
2
3  FileName    [imgTfmCache.c]
4
5  PackageName [img]
6
7  Synopsis    [Routines for image cache in transition function method.]
8
9  SeeAlso     [imgTfm.c imgTfmFwd.c imgTfmBwd.c imgTfmUtil.c]
10
11  Author      [In-Ho Moon]
12
13  Copyright   [Copyright (c) 1994-1996 The Regents of the Univ. of Colorado.
14  All rights reserved.
15
16  Permission is hereby granted, without written agreement and without license
17  or royalty fees, to use, copy, modify, and distribute this software and its
18  documentation for any purpose, provided that the above copyright notice and
19  the following two paragraphs appear in all copies of this software.
20
21  IN NO EVENT SHALL THE UNIVERSITY OF COLORADO BE LIABLE TO ANY PARTY FOR
22  DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES ARISING OUT
23  OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF THE UNIVERSITY OF
24  COLORADO HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25
26  THE UNIVERSITY OF COLORADO SPECIFICALLY DISCLAIMS ANY WARRANTIES,
27  INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
28  FITNESS FOR A PARTICULAR PURPOSE.  THE SOFTWARE PROVIDED HEREUNDER IS ON AN
29  "AS IS" BASIS, AND THE UNIVERSITY OF COLORADO HAS NO OBLIGATION TO PROVIDE
30  MAINTENANCE, SUPPORT, UPDATES, ENHANCEMENTS, OR MODIFICATIONS.]
31
32******************************************************************************/
33#include "imgInt.h"
34
35static char rcsid[] UNUSED = "$Id: imgTfmCache.c,v 1.8 2005/04/23 14:30:54 jinh Exp $";
36
37/*---------------------------------------------------------------------------*/
38/* Constant declarations                                                     */
39/*---------------------------------------------------------------------------*/
40
41/*---------------------------------------------------------------------------*/
42/* Type declarations                                                         */
43/*---------------------------------------------------------------------------*/
44
45/*---------------------------------------------------------------------------*/
46/* Structure declarations                                                    */
47/*---------------------------------------------------------------------------*/
48
49/*---------------------------------------------------------------------------*/
50/* Variable declarations                                                     */
51/*---------------------------------------------------------------------------*/
52
53static  int             ComplementFlag; /* If set, returns the negation of the
54                                           result from cache */
55static  array_t         *SubstituteVector; /* returns the result from cache by
56                                              substituting the variables */
57static  ImgCacheTable_t *ImgGlobalCache; /* global image cache */
58static  ImgCacheTable_t *PreGlobalCache; /* global preimage cache */
59static  int             ImgGlobalCacheRef; /* the number of image-info
60                                              refering to the image cache */
61static  int             PreGlobalCacheRef; /* the number of image-info
62                                              refering to the preimage cache */
63
64/*---------------------------------------------------------------------------*/
65/* Macro declarations                                                        */
66/*---------------------------------------------------------------------------*/
67
68
69/**AutomaticStart*************************************************************/
70
71/*---------------------------------------------------------------------------*/
72/* Static function prototypes                                                */
73/*---------------------------------------------------------------------------*/
74
75static void CacheDestroyEntry(ImgCacheEntry_t *entry, boolean freeEntry);
76static int VectorHash(ImgCacheTable_t *table, array_t *delta, bdd_t *constraint);
77static int VectorStHash(char *key, int modulus);
78static int KeyStHash(char *key, int modulus);
79static int VectorCompare(array_t *vector1, array_t *vector2);
80static int VectorSortCompare(array_t *vector1, array_t *vector2);
81static int VectorSortCompareWithConstraint(array_t *vector1, array_t *vector2);
82static int ImageKeyCompare(ImgCacheStKey_t *key1, ImgCacheStKey_t *key2);
83static int ImageKeySortCompare(ImgCacheStKey_t *key1, ImgCacheStKey_t *key2);
84static int PreImageKeyCompare(ImgCacheStKey_t *key1, ImgCacheStKey_t *key2);
85static mdd_t * SubstituteCacheResult(ImgTfmInfo_t *info, array_t *keyVector, array_t *cacheVector, mdd_t *result);
86static mdd_t * SubstituteCacheResultRecur(mdd_t *result, array_t *varArray, array_t *funcArray, int pos);
87
88/**AutomaticEnd***************************************************************/
89
90
91/*---------------------------------------------------------------------------*/
92/* Definition of exported functions                                          */
93/*---------------------------------------------------------------------------*/
94
95
96/**Function********************************************************************
97
98  Synopsis    [Gets the statistics of image cache of transition function
99  method.]
100
101  Description [Gets the statistics of image cache of transition function
102  method]
103
104  SideEffects []
105
106  SeeAlso     []
107
108******************************************************************************/
109int
110Img_TfmGetCacheStatistics(Img_ImageInfo_t *imageInfo, int preFlag,
111                          double *inserts, double *lookups, double *hits,
112                          double *entries, int *nSlots, int *maxChainLength)
113{
114  ImgTfmInfo_t          *info;
115  ImgCacheTable_t       *cache;
116
117  if (imageInfo) {
118    if (imageInfo->methodType != Img_Tfm_c &&
119        imageInfo->methodType != Img_Hybrid_c) {
120      return(0);
121    }
122
123    info = (ImgTfmInfo_t *)imageInfo->methodData;
124    if (!info->option->useCache)
125      return(0);
126
127    if (preFlag)
128      cache = info->preCache;
129    else
130      cache = info->imgCache;
131    if (!cache)
132      return(0);
133  } else {
134    if (preFlag)
135      cache = PreGlobalCache;
136    else
137      cache = ImgGlobalCache;
138    if (!cache)
139      return(0);
140  }
141
142  *inserts = cache->inserts;
143  *lookups = cache->lookups;
144  *hits = cache->hits;
145  *entries = cache->entries;
146  if (cache->stTable) {
147    *nSlots = 0;
148    *maxChainLength = 0;
149  } else {
150    *nSlots = cache->nSlots;
151    *maxChainLength = cache->maxChainLength;
152  }
153  return(1);
154}
155
156
157/**Function********************************************************************
158
159  Synopsis    [Checks whether a global cache is used for transition function
160  method.]
161
162  Description [Checks whether a global cache is used for transition function
163  method. If it is, returns 1, otherwise returns 0.
164  A global cache can be used when all image-info structs store the results
165  into one image cache. A local cache is used for each image-info struct stores
166  its results into its own image cache.]
167
168  SideEffects []
169
170  SeeAlso     []
171
172******************************************************************************/
173int
174Img_TfmCheckGlobalCache(int preFlag)
175{
176  if (preFlag) {
177    if (PreGlobalCache)
178      return(1);
179    else
180      return(0);
181  } else {
182    if (ImgGlobalCache)
183      return(1);
184    else
185      return(0);
186  }
187}
188
189
190/**Function********************************************************************
191
192  Synopsis    [Prints the statistics of image cache of transition function
193  method.]
194
195  Description [Prints the statistics of image cache of transition function
196  method.]
197
198  SideEffects []
199
200  SeeAlso     []
201
202******************************************************************************/
203void
204Img_TfmPrintCacheStatistics(Img_ImageInfo_t *imageInfo, int preFlag)
205{
206  ImgTfmInfo_t          *info;
207  ImgCacheTable_t       *cache;
208
209  if (imageInfo) {
210    if (imageInfo->methodType != Img_Tfm_c &&
211        imageInfo->methodType != Img_Hybrid_c) {
212      return;
213    }
214
215    info = (ImgTfmInfo_t *)imageInfo->methodData;
216    if (!info->option->useCache)
217      return;
218
219    if (preFlag)
220      cache = info->preCache;
221    else
222      cache = info->imgCache;
223    if (!cache)
224      return;
225  } else {
226    if (preFlag)
227      cache = PreGlobalCache;
228    else
229      cache = ImgGlobalCache;
230    if (!cache)
231      return;
232  }
233  ImgPrintCacheStatistics(cache);
234}
235
236
237/**Function********************************************************************
238
239  Synopsis    [Frees all cache contents of image computation using transition
240  function method.]
241
242  Description [Frees all cache contents of image computation using transition
243  function method. This function is to free the cache contents only when
244  requested and when tfm_auto_flush_cache is off.]
245
246  SideEffects []
247
248  SeeAlso     []
249
250******************************************************************************/
251void
252Img_TfmFlushCache(Img_ImageInfo_t *imageInfo, int preFlag)
253{
254  ImgTfmInfo_t  *info;
255
256  if (imageInfo) {
257    if (imageInfo->methodType != Img_Tfm_c &&
258        imageInfo->methodType != Img_Hybrid_c) {
259      return;
260    }
261
262    info = (ImgTfmInfo_t *)imageInfo->methodData;
263
264    if (info->option->autoFlushCache == 0) {
265      if (preFlag)
266        ImgFlushCache(info->preCache);
267      else
268        ImgFlushCache(info->imgCache);
269    }
270  }
271}
272
273
274/*---------------------------------------------------------------------------*/
275/* Definition of internal functions                                          */
276/*---------------------------------------------------------------------------*/
277
278
279/**Function********************************************************************
280
281  Synopsis    [Initializes a cache table.]
282
283  Description [Initializes a cache table.]
284
285  SideEffects []
286
287******************************************************************************/
288void
289ImgCacheInitTable(ImgTfmInfo_t *info, int num_slot, int globalCache,
290                boolean preImgFlag)
291{
292  ImgCacheTable_t       *table;
293  ImgTfmOption_t        *option = info->option;
294
295  if (globalCache) {
296    if (preImgFlag && PreGlobalCache) {
297      info->preCache = PreGlobalCache;
298      PreGlobalCacheRef++;
299      return;
300    } else if (!preImgFlag && ImgGlobalCache) {
301      info->imgCache = ImgGlobalCache;
302      ImgGlobalCacheRef++;
303      return;
304    }
305  }
306
307  table = ALLOC(ImgCacheTable_t, 1);
308  memset(table, 0, sizeof(ImgCacheTable_t));
309  table->nSlots = num_slot;
310  if (option->useCache == 2) {
311    if (preImgFlag)
312      table->stTable = st_init_table((ST_PFICPCP)PreImageKeyCompare,
313                                     KeyStHash);
314    else if (info->useConstraint && option->sortVectorFlag)
315      table->stTable = st_init_table((ST_PFICPCP)ImageKeySortCompare,
316                                     KeyStHash);
317    else if (info->useConstraint)
318      table->stTable = st_init_table((ST_PFICPCP)ImageKeyCompare,
319                                     KeyStHash);
320    else if (option->sortVectorFlag)
321      table->stTable = st_init_table((ST_PFICPCP)VectorSortCompare,
322                                     VectorStHash);
323    else
324      table->stTable = st_init_table((ST_PFICPCP)VectorCompare,
325                                     VectorStHash);
326  } else {
327    table->slot = ALLOC(ImgCacheEntry_t *, num_slot);
328    memset(table->slot, 0, sizeof(ImgCacheEntry_t *) * num_slot);
329  }
330  table->maxChainLength = option->maxChainLength;
331  table->preImgFlag = preImgFlag;
332  table->useConstraint = info->useConstraint;
333  if (preImgFlag) {
334    table->compareFunc = VectorCompare;
335    info->preCache = table;
336  } else {
337    if (option->sortVectorFlag) {
338      if (info->useConstraint)
339        table->compareFunc = VectorSortCompareWithConstraint;
340      else
341        table->compareFunc = VectorSortCompare;
342    } else
343      table->compareFunc = VectorCompare;
344    info->imgCache = table;
345  }
346
347  if (globalCache) {
348    if (preImgFlag) {
349      PreGlobalCache = table;
350      PreGlobalCacheRef = 1;
351    } else {
352      ImgGlobalCache = table;
353      ImgGlobalCacheRef = 1;
354    }
355  }
356}
357
358
359/**Function********************************************************************
360
361  Synopsis    [Destroys a cache table.]
362
363  Description [Destroys a cache table.]
364
365  SideEffects []
366
367******************************************************************************/
368void
369ImgCacheDestroyTable(ImgCacheTable_t *table, int globalCache)
370{
371  unsigned int          i;
372  ImgCacheEntry_t       *entry, *next;
373  array_t               *vector;
374  bdd_t                 *result;
375  st_generator          *stGen;
376  ImgCacheStKey_t       *key;
377
378  if (globalCache) {
379    if (table->preImgFlag) {
380      PreGlobalCacheRef--;
381      if (PreGlobalCacheRef > 0)
382        return;
383    } else {
384      ImgGlobalCacheRef--;
385      if (ImgGlobalCacheRef > 0)
386        return;
387    }
388  }
389
390  if (table->stTable) {
391    if (table->preImgFlag || table->useConstraint) {
392      st_foreach_item(table->stTable, stGen, &key, &result) {
393        ImgVectorFree(key->vector);
394        if (key->constraint)
395          mdd_free(key->constraint);
396        FREE(key);
397        mdd_free(result);
398      }
399    } else {
400      st_foreach_item(table->stTable, stGen, &vector, &result) {
401        ImgVectorFree(vector);
402        mdd_free(result);
403      }
404    }
405    st_free_table(table->stTable);
406  } else {
407    for (i = 0; i < table->nSlots; i++) {
408      entry = table->slot[i];
409      while (entry != NIL(ImgCacheEntry_t)) {
410        next = entry->next;
411        CacheDestroyEntry(entry, TRUE);
412        entry = next;
413      }
414    }
415    FREE(table->slot);
416  }
417
418  if (globalCache) {
419    if (table->preImgFlag)
420      PreGlobalCache = NIL(ImgCacheTable_t);
421    else
422      ImgGlobalCache = NIL(ImgCacheTable_t);
423  }
424
425  FREE(table);
426}
427
428
429/**Function********************************************************************
430
431  Synopsis    [Lookups cache table.]
432
433  Description [Lookups cache table.]
434
435  SideEffects []
436
437******************************************************************************/
438bdd_t *
439ImgCacheLookupTable(ImgTfmInfo_t *info, ImgCacheTable_t *table, array_t *delta,
440                    bdd_t *constraint)
441{
442  int                   slot;
443  ImgCacheEntry_t       *entry;
444  bdd_t                 *result, *newResult;
445  int                   *ptr1, *ptr2;
446  ImgCacheStKey_t       key;
447
448  table->lookups += 1.0;
449
450  /* lossless cache */
451  if (table->stTable) {
452    if (table->preImgFlag) {
453      key.vector = delta;
454      key.constraint = constraint;
455      if (st_lookup(table->stTable, (char *)&key, &result)) {
456        table->hits += 1.0;
457        if (ComplementFlag)
458          return(mdd_not(result));
459        else
460          return(mdd_dup(result));
461      }
462    } else if (table->useConstraint) {
463      key.vector = delta;
464      key.constraint = constraint;
465      if (st_lookup(table->stTable, (char *)&key, &result)) {
466        table->hits += 1.0;
467        if (SubstituteVector) {
468          newResult = SubstituteCacheResult(info, delta, SubstituteVector,
469                                            result);
470          return(newResult);
471        } else
472          return(mdd_dup(result));
473      }
474    } else {
475      if (st_lookup(table->stTable, (char *)delta, &result)) {
476        table->hits += 1.0;
477        if (SubstituteVector) {
478          newResult = SubstituteCacheResult(info, delta, SubstituteVector,
479                                            result);
480          return(newResult);
481        }
482        return(mdd_dup(result));
483      }
484    }
485
486    return(NIL(bdd_t));
487  }
488
489  slot = VectorHash(table, delta, constraint);
490
491  entry = table->slot[slot];
492  while (entry != NIL(ImgCacheEntry_t)) {
493    if ((*table->compareFunc)(delta, entry->vector) == 0) {
494      table->hits++;
495      if (table->preImgFlag) { /* preimage computation */
496        ptr1 = (int *)bdd_pointer(constraint);
497        ptr2 = (int *)bdd_pointer(entry->constraint);
498        if (((unsigned long)ptr1 ^ (unsigned long)ptr2) <= 01) {
499          table->hits++;
500          if (mdd_equal(constraint, entry->constraint))
501            return(mdd_dup(entry->result));
502          else
503            return(mdd_not(entry->result));
504        }
505      } else if (constraint) { /* image computation */
506        if (mdd_equal(constraint, entry->constraint)) {
507          if (SubstituteVector) {
508            newResult = SubstituteCacheResult(info, delta, SubstituteVector,
509                                                entry->result);
510            return(newResult);
511          }
512          return(mdd_dup(entry->result));
513        }
514      } else if (SubstituteVector) { /* range computation */
515        newResult = SubstituteCacheResult(info, delta, SubstituteVector,
516                                          entry->result);
517        return(newResult);
518      } else {
519        return(mdd_dup(entry->result));
520      }
521    }
522    entry = entry->next;
523  }
524  return(NIL(bdd_t));
525}
526
527
528/**Function********************************************************************
529
530  Synopsis    [Inserts an entry into cache table.]
531
532  Description [Inserts an entry into cache table.]
533
534  SideEffects []
535
536******************************************************************************/
537void
538ImgCacheInsertTable(ImgCacheTable_t *table, array_t *delta,
539                    bdd_t *constraint, bdd_t *result)
540{
541  int                   slot, num, minSize;
542  ImgCacheEntry_t       *entry, *new_, *pos, *minDeltaEntry;
543
544  table->inserts += 1.0;
545
546  if (table->stTable) {
547    table->entries += 1.0;
548    if (table->preImgFlag || table->useConstraint) {
549      ImgCacheStKey_t   *key;
550
551      key = ALLOC(ImgCacheStKey_t, 1);
552      key->vector = delta;
553      key->constraint = constraint;
554      st_insert(table->stTable, (char *)key, (char *)result);
555    } else
556      st_insert(table->stTable, (char *)delta, (char *)result);
557    return;
558  }
559
560  slot = VectorHash(table, delta, constraint);
561
562  minSize = 0x7fffffff;
563  num = 0;
564  pos = table->slot[slot];
565  entry = minDeltaEntry = NIL(ImgCacheEntry_t);
566  while (pos != NIL(ImgCacheEntry_t)) {
567    if (array_n(pos->vector) < minSize) {
568      minDeltaEntry = pos;
569      minSize = array_n(pos->vector);
570    }
571    pos = pos->next;
572    num++;
573  }
574
575  /* num = the number entries in the slot */
576  if (num < table->maxChainLength) {
577    new_ = ALLOC(ImgCacheEntry_t, 1);
578    new_->vector = delta;
579    new_->constraint = constraint;
580    new_->result = result;
581    new_->next = table->slot[slot];
582    table->slot[slot] = new_;
583    table->entries += 1.0;
584  } else if (entry != NIL(ImgCacheEntry_t)) {
585    CacheDestroyEntry(entry, FALSE);
586    entry->vector = delta;
587    entry->constraint = constraint;
588    entry->result = result;
589  } else { /* all entries are full of latest entries */
590    if (0) { /* Rehash */
591      unsigned int      i, new_num_slot, new_slot, old_num_slot;
592      ImgCacheEntry_t   *next;
593      ImgCacheEntry_t   **old_bin;
594
595      old_num_slot = table->nSlots;
596      old_bin = table->slot;
597      new_num_slot = old_num_slot * 2;
598      table->slot = ALLOC(ImgCacheEntry_t *, new_num_slot);
599      if (!table->slot) {
600        printf("VI_insert_table:new_slots");
601        exit(-1);
602      }
603      memset(table->slot, 0, sizeof(ImgCacheEntry_t *) * new_num_slot);
604      table->nSlots = new_num_slot;
605
606      for (i = 0; i < old_num_slot; i++) {
607        pos = old_bin[i];
608        while (pos != NIL(ImgCacheEntry_t)) {
609          next = pos->next;
610          new_slot = VectorHash(table, pos->vector, pos->constraint);
611          pos->next = table->slot[new_slot];
612          table->slot[new_slot] = pos;
613          pos = next;
614        }
615      }
616
617      new_slot = VectorHash(table, delta, constraint);
618      new_ = ALLOC(ImgCacheEntry_t, 1);
619      new_->vector = delta;
620      new_->constraint = constraint;
621      new_->result = result;
622      new_->next = table->slot[slot];
623      table->slot[slot] = new_;
624      table->entries += 1.0;
625    } else {
626      CacheDestroyEntry(minDeltaEntry, FALSE);
627      minDeltaEntry->vector = delta;
628      minDeltaEntry->constraint = constraint;
629      minDeltaEntry->result = result;
630    }
631  }
632}
633
634
635/**Function********************************************************************
636
637  Synopsis    [Flushes all cache entries.]
638
639  Description [Flushes all cache entries.]
640
641  SideEffects []
642
643******************************************************************************/
644void
645ImgFlushCache(ImgCacheTable_t *table)
646{
647  unsigned int          i;
648  ImgCacheEntry_t       *entry, *next;
649  array_t               *vector;
650  bdd_t                 *result;
651  st_generator          *stGen;
652  ImgCacheStKey_t       *key;
653
654  if (!table)
655    return;
656
657  if (table->stTable) {
658    if (table->preImgFlag || table->useConstraint) {
659      st_foreach_item(table->stTable, stGen, &key, &result) {
660        st_delete(table->stTable, &key, NIL(char *));
661        ImgVectorFree(key->vector);
662        mdd_free(key->constraint);
663        FREE(key);
664        mdd_free(result);
665      }
666    } else {
667      st_foreach_item(table->stTable, stGen, &vector, &result) {
668        st_delete(table->stTable, &vector, NIL(char *));
669        ImgVectorFree(vector);
670        mdd_free(result);
671      }
672    }
673  } else {
674    for (i = 0; i < table->nSlots; i++) {
675      entry = table->slot[i];
676      while (entry != NIL(ImgCacheEntry_t)) {
677        next = entry->next;
678        CacheDestroyEntry(entry, TRUE);
679        entry = next;
680      }
681      table->slot[i] = NIL(ImgCacheEntry_t);
682    }
683  }
684  table->entries = 0.0;
685}
686
687
688/**Function********************************************************************
689
690  Synopsis    [Prints cache statistics for transition function method.]
691
692  Description [Prints cache statistics for transition function method.]
693
694  SideEffects []
695
696  SeeAlso     []
697
698******************************************************************************/
699void
700ImgPrintCacheStatistics(ImgCacheTable_t *cache)
701{
702  if (cache->preImgFlag)
703    fprintf(vis_stdout, "** cache statistics (preImg) **\n");
704  else
705    fprintf(vis_stdout, "** cache statistics (img) **\n");
706  fprintf(vis_stdout, "# insertions = %g\n", cache->inserts);
707  if (cache->inserts != 0.0) {
708    fprintf(vis_stdout, "# lookups = %g\n", cache->lookups);
709    fprintf(vis_stdout, "# hits = %g (%.2f%%)\n", cache->hits,
710        cache->hits / cache->lookups * 100.0);
711    fprintf(vis_stdout, "# misses = %g (%.2f%%)\n",
712        cache->lookups - cache->hits,
713        (cache->lookups - cache->hits) / cache->lookups * 100.0);
714    fprintf(vis_stdout, "# entries = %g\n", cache->entries);
715    if (!cache->stTable) {
716      fprintf(vis_stdout, "# slots = %d\n", cache->nSlots);
717      fprintf(vis_stdout, "maxChainLength = %d\n", cache->maxChainLength);
718    }
719  }
720}
721
722
723/*---------------------------------------------------------------------------*/
724/* Definition of static functions                                            */
725/*---------------------------------------------------------------------------*/
726
727
728/**Function********************************************************************
729
730  Synopsis    [Destroys a cache entry.]
731
732  Description [Destroys a cache entry.]
733
734  SideEffects []
735
736******************************************************************************/
737static void
738CacheDestroyEntry(ImgCacheEntry_t *entry, boolean freeEntry)
739{
740  ImgVectorFree(entry->vector);
741  mdd_free(entry->result);
742  if (entry->constraint)
743    mdd_free(entry->constraint);
744  if (freeEntry)
745    FREE(entry);
746}
747
748
749/**Function********************************************************************
750
751  Synopsis    [Returns hash value of a vector.]
752
753  Description [Returns hash value of a vector.]
754
755  SideEffects []
756
757******************************************************************************/
758static int
759VectorHash(ImgCacheTable_t *table, array_t *delta, bdd_t *constraint)
760{
761  unsigned long         value;
762  ImgComponent_t        *comp;
763  bdd_t                 *func;
764  int                   i;
765
766  value = array_n(delta);
767  if (constraint)
768    value += (unsigned long)bdd_pointer(constraint) & ~01;
769  for (i = 0; i < array_n(delta); i++) {
770    comp = array_fetch(ImgComponent_t *, delta, i);
771    func = comp->func;
772    value += (unsigned long)bdd_pointer(func) & ~01;
773  }
774  return((int)(value % table->nSlots));
775}
776
777
778/**Function********************************************************************
779
780  Synopsis    [Returns hash value of a vector for st_table.]
781
782  Description [Returns hash value of a vector for st_table.]
783
784  SideEffects []
785
786******************************************************************************/
787static int
788VectorStHash(char *key, int modulus)
789{
790  unsigned long         value;
791  array_t               *delta;
792  ImgComponent_t        *comp;
793  bdd_t                 *func;
794  int                   i;
795
796  delta = (array_t *)key;
797  value = array_n(delta);
798
799  for (i = 0; i < array_n(delta); i++) {
800    comp = array_fetch(ImgComponent_t *, delta, i);
801    func = comp->func;
802    value += (unsigned long)bdd_pointer(func) & ~01;
803  }
804  return((int)(value % modulus));
805}
806
807
808/**Function********************************************************************
809
810  Synopsis    [Returns hash value of a key for st_table.]
811
812  Description [Returns hash value of a key for st_table.]
813
814  SideEffects []
815
816******************************************************************************/
817static int
818KeyStHash(char *key, int modulus)
819{
820  ImgCacheStKey_t       *stKey;
821  unsigned long         value;
822  array_t               *delta;
823  ImgComponent_t        *comp;
824  bdd_t                 *func;
825  int                   i;
826
827  stKey = (ImgCacheStKey_t *)key;
828  delta = stKey->vector;
829  value = array_n(delta);
830  if (stKey->constraint)
831    value += (unsigned long)bdd_pointer(stKey->constraint) & ~01;
832
833  for (i = 0; i < array_n(delta); i++) {
834    comp = array_fetch(ImgComponent_t *, delta, i);
835    func = comp->func;
836    value += (unsigned long)bdd_pointer(func) & ~01;
837  }
838  return((int)(value % modulus));
839}
840
841
842/**Function********************************************************************
843
844  Synopsis    [Compares two vectors.]
845
846  Description [Compares two vectors.]
847
848  SideEffects []
849
850******************************************************************************/
851static int
852VectorCompare(array_t *vector1, array_t *vector2)
853{
854  ImgComponent_t        *comp1, *comp2;
855  int                   i, index1, index2;
856
857  if (array_n(vector1) != array_n(vector2))
858    return(1);
859
860  for (i = 0; i < array_n(vector1); i++) {
861    comp1 = array_fetch(ImgComponent_t *, vector1, i);
862    comp2 = array_fetch(ImgComponent_t *, vector2, i);
863    index1 = (int)bdd_top_var_id(comp1->var);
864    index2 = (int)bdd_top_var_id(comp2->var);
865    if (index1 != index2)
866      return(1);
867    if (!mdd_equal(comp1->func, comp2->func))
868      return(1);
869  }
870  SubstituteVector = NIL(array_t);
871  return(0);
872}
873
874
875/**Function********************************************************************
876
877  Synopsis    [Compares two vectors considering substitution.]
878
879  Description [Compares two vectors considering substitution.]
880
881  SideEffects []
882
883******************************************************************************/
884static int
885VectorSortCompare(array_t *vector1, array_t *vector2)
886{
887  ImgComponent_t        *comp1, *comp2;
888  int                   i, index1, index2;
889  int                   *ptr1, *ptr2, *regularPtr1, *regularPtr2;
890
891  if (array_n(vector1) != array_n(vector2))
892    return(1);
893
894  SubstituteVector = NIL(array_t);
895  for (i = 0; i < array_n(vector1); i++) {
896    comp1 = array_fetch(ImgComponent_t *, vector1, i);
897    comp2 = array_fetch(ImgComponent_t *, vector2, i);
898    index1 = (int)bdd_top_var_id(comp1->var);
899    index2 = (int)bdd_top_var_id(comp2->var);
900    if (index1 != index2)
901      SubstituteVector = vector2;
902    ptr1 = (int *)bdd_pointer(comp1->func);
903    ptr2 = (int *)bdd_pointer(comp2->func);
904    regularPtr1 = (int *)((unsigned long)ptr1 & ~01);
905    regularPtr2 = (int *)((unsigned long)ptr2 & ~01);
906    if (regularPtr1 == regularPtr2) {
907      if (ptr1 != ptr2) {
908        if (comp1->intermediate || comp2->intermediate)
909          return(1);
910        SubstituteVector = vector2;
911      }
912    } else
913      return(1);
914  }
915  return(0);
916}
917
918
919/**Function********************************************************************
920
921  Synopsis    [Compares two vectors considering substitution.]
922
923  Description [Compares two vectors considering substitution.]
924
925  SideEffects []
926
927******************************************************************************/
928static int
929VectorSortCompareWithConstraint(array_t *vector1, array_t *vector2)
930{
931  ImgComponent_t        *comp1, *comp2;
932  int                   i, index1, index2;
933
934  if (array_n(vector1) != array_n(vector2))
935    return(1);
936
937  SubstituteVector = NIL(array_t);
938  for (i = 0; i < array_n(vector1); i++) {
939    comp1 = array_fetch(ImgComponent_t *, vector1, i);
940    comp2 = array_fetch(ImgComponent_t *, vector2, i);
941    index1 = (int)bdd_top_var_id(comp1->var);
942    index2 = (int)bdd_top_var_id(comp2->var);
943    if (index1 != index2)
944      SubstituteVector = vector2;
945    if (!mdd_equal(comp1->func, comp2->func))
946      return(1);
947  }
948  return(0);
949}
950
951
952/**Function********************************************************************
953
954  Synopsis    [Compares two keys.]
955
956  Description [Compares two keys.]
957
958  SideEffects []
959
960******************************************************************************/
961static int
962ImageKeyCompare(ImgCacheStKey_t *key1, ImgCacheStKey_t *key2)
963{
964  ComplementFlag = 0;
965  if (mdd_equal(key1->constraint, key2->constraint)) {
966    if (VectorCompare(key1->vector, key2->vector))
967      return(1);
968  } else
969    return(1);
970  return(0);
971}
972
973
974/**Function********************************************************************
975
976  Synopsis    [Compares two keys considering substitution.]
977
978  Description [Compares two keys considering substitution.]
979
980  SideEffects []
981
982******************************************************************************/
983static int
984ImageKeySortCompare(ImgCacheStKey_t *key1, ImgCacheStKey_t *key2)
985{
986  ComplementFlag = 0;
987  if (mdd_equal(key1->constraint, key2->constraint)) {
988    if (VectorSortCompareWithConstraint(key1->vector, key2->vector))
989      return(1);
990  } else
991    return(1);
992  return(0);
993}
994
995
996/**Function********************************************************************
997
998  Synopsis    [Compares two keys for preimage.]
999
1000  Description [Compares two keys for preimage.]
1001
1002  SideEffects []
1003
1004******************************************************************************/
1005static int
1006PreImageKeyCompare(ImgCacheStKey_t *key1, ImgCacheStKey_t *key2)
1007{
1008  unsigned long ptr1, ptr2;
1009
1010  ptr1 = (unsigned long)bdd_pointer(key1->constraint);
1011  ptr2 = (unsigned long)bdd_pointer(key2->constraint);
1012  if ((ComplementFlag = (int) (ptr1 ^ ptr2)) <= 01) {
1013    if (VectorCompare(key1->vector, key2->vector))
1014      return(1);
1015  } else
1016    return(1);
1017  return(0);
1018}
1019
1020
1021/**Function********************************************************************
1022
1023  Synopsis    [Substitutes a cache result.]
1024
1025  Description [Substitutes a cache result.]
1026
1027  SideEffects []
1028
1029******************************************************************************/
1030static mdd_t *
1031SubstituteCacheResult(ImgTfmInfo_t *info, array_t *keyVector,
1032                      array_t *cacheVector,
1033                        mdd_t *result)
1034{
1035  mdd_t                 *newResult;
1036  ImgComponent_t        *comp1, *comp2;
1037  int                   *ptr1, *ptr2;
1038  int                   i, id1, id2;
1039  mdd_t                 *var, *func;
1040  array_t               *varArray, *funcArray;
1041
1042  varArray = array_alloc(mdd_t *, 0);
1043  funcArray = array_alloc(mdd_t *, 0);
1044
1045  for (i = 0; i < array_n(keyVector); i++) {
1046    comp1 = array_fetch(ImgComponent_t *, keyVector, i);
1047    comp2 = array_fetch(ImgComponent_t *, cacheVector, i);
1048    ptr1 = (int *)bdd_pointer(comp1->func);
1049    ptr2 = (int *)bdd_pointer(comp2->func);
1050    id1 = (int)bdd_top_var_id(comp1->var);
1051    id2 = (int)bdd_top_var_id(comp2->var);
1052    if (id1 == id2) {
1053      if (ptr1 != ptr2) {
1054        array_insert_last(mdd_t *, varArray, comp2->var);
1055        func = mdd_not(comp1->var);
1056        array_insert_last(mdd_t *, funcArray, func);
1057      }
1058    } else {
1059      if (ptr1 == ptr2) {
1060        array_insert_last(mdd_t *, varArray, comp2->var);
1061        func = mdd_dup(comp1->var);
1062        array_insert_last(mdd_t *, funcArray, func);
1063      } else {
1064        array_insert_last(mdd_t *, varArray, comp2->var);
1065        func = mdd_not(comp1->var);
1066        array_insert_last(mdd_t *, funcArray, func);
1067      }
1068    }
1069  }
1070  if (array_n(varArray) == 1) {
1071    var = array_fetch(mdd_t *, varArray, 0);
1072    func = array_fetch(mdd_t *, funcArray, 0);
1073    newResult = bdd_compose(result, var, func);
1074  } else if (bdd_get_package_name() == CUDD)
1075    newResult = bdd_vector_compose(result, varArray, funcArray);
1076  else
1077    newResult = SubstituteCacheResultRecur(result, varArray, funcArray, 0);
1078  array_free(varArray);
1079  mdd_array_free(funcArray);
1080  return(newResult);
1081}
1082
1083
1084/**Function********************************************************************
1085
1086  Synopsis    [Recursive procedure of SubstituteCacheResult.]
1087
1088  Description [Recursive procedure of SubstituteCacheResult.]
1089
1090  SideEffects []
1091
1092******************************************************************************/
1093static mdd_t *
1094SubstituteCacheResultRecur(mdd_t *result, array_t *varArray, array_t *funcArray,
1095                           int pos)
1096{
1097  mdd_t *var, *varNot, *func;
1098  mdd_t *resultT, *resultE, *newResultT, *newResultE, *newResult;
1099
1100  if (pos > array_n(varArray))
1101    return(mdd_dup(result));
1102
1103  var = array_fetch(mdd_t *, varArray, pos);
1104  func = array_fetch(mdd_t *, funcArray, pos);
1105  varNot = mdd_not(var);
1106  resultT = bdd_cofactor(result, var);
1107  resultE = bdd_cofactor(result, varNot);
1108  mdd_free(varNot);
1109  newResultT = SubstituteCacheResultRecur(resultT, varArray, funcArray,
1110                                          pos + 1);
1111  mdd_free(resultT);
1112  newResultE = SubstituteCacheResultRecur(resultE, varArray, funcArray,
1113                                          pos + 1);
1114  mdd_free(resultE);
1115  newResult = bdd_ite(func, newResultT, newResultE, 1, 1, 1);
1116  mdd_free(newResultT);
1117  mdd_free(newResultE);
1118  return(newResult);
1119}
Note: See TracBrowser for help on using the repository browser.