1 /*
2 * gcrChannel.c -
3 *
4 * Channel manipulation: allocation, freeing, and transforming
5 * (e.g, flipping them left-to-right or rotating). Transforming
6 * is done so that the channel can be routed in the easiest
7 * direction.
8 *
9 * *********************************************************************
10 * * Copyright (C) 1985, 1990 Regents of the University of California. *
11 * * Permission to use, copy, modify, and distribute this *
12 * * software and its documentation for any purpose and without *
13 * * fee is hereby granted, provided that the above copyright *
14 * * notice appear in all copies. The University of California *
15 * * makes no representations about the suitability of this *
16 * * software for any purpose. It is provided "as is" without *
17 * * express or implied warranty. Export of this software outside *
18 * * of the United States of America may require an export license. *
19 * *********************************************************************
20 */
21
22 #ifndef lint
23 static char rcsid[] __attribute__ ((unused)) = "$Header: /usr/cvsroot/magic-8.0/gcr/gcrChannel.c,v 1.1.1.1 2008/02/03 20:43:50 tim Exp $";
24 #endif /* not lint */
25
26 #include <stdio.h>
27 #include <string.h>
28
29 #include "utils/magic.h"
30 #include "utils/geometry.h"
31 #include "gcr/gcr.h"
32 #include "utils/malloc.h"
33
34
35 /*
36 * ----------------------------------------------------------------------------
37 *
38 * GCRNewChannel --
39 *
40 * This procedure allocates storage for a new channel structure,
41 * and initializes most of the structure.
42 *
43 * Results:
44 * The return value is a pointer to the new channel.
45 *
46 * Side effects:
47 * Storage is allocated. The initial state of the channel is
48 * completely empty, although all pin and result arrays are
49 * allocated. This procedure does not initialize the fields
50 * gcr_area, gcr_origin, or gcr_lCol, although it allocates
51 * storage for gcr_lCol. Also, it doesn't initialize the
52 * value of gcr_point for each pin.
53 *
54 * ----------------------------------------------------------------------------
55 */
56
57 GCRChannel *
GCRNewChannel(length,width)58 GCRNewChannel(length, width)
59 int length; /* Length of the channel (# of columns) */
60 int width; /* Width of the channel (# rows) */
61 {
62 unsigned lenWds, widWds, nBytes;
63 GCRChannel *ch;
64 int i;
65
66 lenWds = length + 2;
67 widWds = width + 2;
68
69 ch = (GCRChannel *) mallocMagic((unsigned) (sizeof (GCRChannel)));
70 ch->gcr_type = CHAN_NORMAL;
71 ch->gcr_length = length;
72 ch->gcr_width = width;
73 ch->gcr_transform = GeoIdentityTransform;
74 ch->gcr_nets = (GCRNet *) NULL;
75
76 /* Malloc storage for pin arrays and zero each */
77 nBytes = lenWds * sizeof (GCRPin);
78 ch->gcr_tPins = (GCRPin *) mallocMagic((unsigned) nBytes);
79 ch->gcr_bPins = (GCRPin *) mallocMagic((unsigned) nBytes);
80 bzero((char *) ch->gcr_tPins, (int) nBytes);
81 bzero((char *) ch->gcr_bPins, (int) nBytes);
82
83 nBytes = widWds * sizeof (GCRPin);
84 ch->gcr_lPins = (GCRPin *) mallocMagic((unsigned) nBytes);
85 ch->gcr_rPins = (GCRPin *) mallocMagic((unsigned) nBytes);
86 bzero((char *) ch->gcr_lPins, (int) nBytes);
87 bzero((char *) ch->gcr_rPins, (int) nBytes);
88
89 ch->gcr_lCol = (GCRColEl *) mallocMagic((unsigned) (widWds * sizeof (GCRColEl)));
90 ch->gcr_density = (int *) mallocMagic((unsigned) (lenWds * sizeof (int)));
91
92 /* Global router-specific initialization */
93 ch->gcr_dRowsByCol = (short *) mallocMagic((unsigned) (lenWds * sizeof (short)));
94 bzero((char *) ch->gcr_dRowsByCol, (int) lenWds * sizeof (short));
95 ch->gcr_dColsByRow = (short *) mallocMagic ((unsigned) (widWds * sizeof (short)));
96 bzero((char *) ch->gcr_dColsByRow, (int) widWds * sizeof (short));
97 ch->gcr_dMaxByRow = ch->gcr_dMaxByCol = 0;
98
99 #ifdef IDENSITY
100 /* For debugging */
101 ch->gcr_iRowsByCol = (short *) mallocMagic((unsigned) (lenWds * sizeof (short)));
102 bzero((char *) ch->gcr_iRowsByCol, (int) lenWds * sizeof (short));
103 ch->gcr_iColsByRow = (short *) mallocMagic((unsigned) (widWds * sizeof (short)));
104 bzero((char *) ch->gcr_iColsByRow, (int) widWds * sizeof (short));
105 #endif /* IDENSITY */
106
107 ch->gcr_client = (ClientData) NULL;
108
109 /* Allocate the result array */
110 ch->gcr_result = (short **) mallocMagic ((unsigned) (lenWds * sizeof (short *)));
111
112 /*
113 * Fill in fields of pins that aren't zero; also allocate
114 * and clear each row of the result array.
115 */
116 nBytes = widWds * sizeof (short);
117 for (i = 0; i < lenWds; i++)
118 {
119 ch->gcr_result[i] = (short *) mallocMagic((unsigned) nBytes);
120 bzero((char *) ch->gcr_result[i], (int) nBytes);
121
122 /* BOTTOM */
123 ch->gcr_bPins[i].gcr_pDist = -1;
124 ch->gcr_bPins[i].gcr_x = i;
125 ch->gcr_bPins[i].gcr_y = 0;
126
127 /* TOP */
128 ch->gcr_tPins[i].gcr_pDist = -1;
129 ch->gcr_tPins[i].gcr_x = i;
130 ch->gcr_tPins[i].gcr_y = widWds - 1;
131 }
132
133 for (i = 0; i < widWds; i++)
134 {
135 /* LEFT */
136 ch->gcr_lPins[i].gcr_pDist = -1;
137 ch->gcr_lPins[i].gcr_x = 0;
138 ch->gcr_lPins[i].gcr_y = i;
139
140 /* RIGHT */
141 ch->gcr_rPins[i].gcr_pDist = -1;
142 ch->gcr_rPins[i].gcr_x = lenWds - 1;
143 ch->gcr_rPins[i].gcr_y = i;
144 }
145
146 return (ch);
147 }
148
149 /*
150 * ----------------------------------------------------------------------------
151 *
152 * GCRFreeChannel --
153 *
154 * This procedure frees up all the storage associated with
155 * a channel
156 *
157 * Results:
158 * None.
159 *
160 * Side effects:
161 * The storage of ch is completely freed. The caller should
162 * refrain from any use of the pointer after this procedure
163 * returns.
164 *
165 * ----------------------------------------------------------------------------
166 */
167
168 void
GCRFreeChannel(ch)169 GCRFreeChannel(ch)
170 GCRChannel *ch; /* Pointer to channel structure to be freed. */
171 {
172 GCRNet *net;
173 int i;
174
175 freeMagic((char *) ch->gcr_tPins);
176 freeMagic((char *) ch->gcr_bPins);
177 freeMagic((char *) ch->gcr_lPins);
178 freeMagic((char *) ch->gcr_rPins);
179 for (net = ch->gcr_nets; net; net = net->gcr_next)
180 freeMagic((char *) net);
181 freeMagic((char *) ch->gcr_lCol);
182
183 freeMagic((char *) ch->gcr_dRowsByCol);
184 freeMagic((char *) ch->gcr_dColsByRow);
185
186 #ifdef IDENSITY
187 /* For debugging */
188 freeMagic((char *) ch->gcr_iRowsByCol);
189 freeMagic((char *) ch->gcr_iColsByRow);
190 #endif /* IDENSITY */
191
192 freeMagic((char *) ch->gcr_density);
193 for (i = 0; i <= ch->gcr_length + 1; i++)
194 freeMagic((char *) ch->gcr_result[i]);
195 freeMagic((char *) ch->gcr_result);
196 freeMagic((char *) ch);
197 }
198
199 /*
200 * ----------------------------------------------------------------------------
201 *
202 * GCRFlipLeftRight --
203 *
204 * This procedure will flip the contents of a channel left-to-right.
205 *
206 * Results:
207 * None.
208 *
209 * Side effects:
210 * The contents of channel dst are modified so that they are
211 * a left-to-right flip of src. Only the four pin arrays, the
212 * transform, the origin, the area, and the result array are
213 * modified. The other fields of dst are untouched. This means,
214 * in particular, that this procedure should be called BEFORE
215 * the linked lists for nets get set up, or else AFTER all the
216 * channel routing has been done and the nets have been freed up.
217 * Also, this procedure does not transform the flag bits GCRTE or
218 * GCRCE, so this procedure shouldn't be called when those flags
219 * are significant.
220 *
221 * ----------------------------------------------------------------------------
222 */
223
224 void
GCRFlipLeftRight(src,dst)225 GCRFlipLeftRight(src, dst)
226 GCRChannel *src; /* Original channel. */
227 GCRChannel *dst; /* Channel to be modified to contain
228 * transformed info from src. The two
229 * channels must have the same dimensions,
230 * but must not be the same channel.
231 */
232 {
233 int y, lenWds, widWds;
234 short old, new;
235 int i, j;
236 Transform t;
237
238 ASSERT(src->gcr_length == dst->gcr_length, "GCRFlipLeftRight: mismatch");
239 ASSERT(src->gcr_width == dst->gcr_width, "GCRFlipLeftRight: mismatch");
240
241 lenWds = src->gcr_length + 1;
242 widWds = src->gcr_width + 1;
243
244 for (i = 0; i <= lenWds; i++)
245 {
246 j = lenWds - i;
247
248 /* Exchange pairs of pins in the top and bottom arrays */
249 dst->gcr_tPins[j] = src->gcr_tPins[i];
250 dst->gcr_tPins[j].gcr_x = j;
251 dst->gcr_bPins[j] = src->gcr_bPins[i];
252 dst->gcr_bPins[j].gcr_x = j;
253
254 /*
255 * Go through the result array, exchanging flag values. Also,
256 * be careful to switch the left-right hazard bits now that the
257 * sense of the channel is reversed. Also switch the GCRR bit
258 * in case there's been routing done.
259 */
260 for (y = 0; y <= widWds; y++)
261 {
262 old = src->gcr_result[i][y];
263 new = old & ~(GCRVR|GCRVL|GCRR);
264 if (old & GCRVR) new |= GCRVL;
265 if (old & GCRVL) new |= GCRVR;
266 if (i != 0 && (src->gcr_result[i-1][y] & GCRR))
267 new |= GCRR;
268 dst->gcr_result[j][y] = new;
269 }
270 }
271
272 /* Switch the left and right end pins */
273 for (i = 0; i <= widWds; i++)
274 {
275 dst->gcr_lPins[i] = src->gcr_rPins[i];
276 dst->gcr_lPins[i].gcr_x = 0;
277 dst->gcr_rPins[i] = src->gcr_lPins[i];
278 dst->gcr_rPins[i].gcr_x = widWds;
279 }
280
281 /* Copy the horizontal and vertical density information */
282 dst->gcr_dMaxByCol = src->gcr_dMaxByCol;
283 dst->gcr_dMaxByRow = src->gcr_dMaxByRow;
284 bcopy((char *) src->gcr_dColsByRow, (char *) dst->gcr_dColsByRow,
285 sizeof (short) * widWds);
286 #ifdef IDENSITY
287 bcopy((char *) src->gcr_iColsByRow, (char *) dst->gcr_iColsByRow,
288 sizeof (short) * widWds);
289 #endif /* IDENSITY */
290 for (i = 0; i <= lenWds; i++)
291 {
292 /* Flip left-to-right */
293 j = lenWds - i;
294 dst->gcr_dRowsByCol[j] = src->gcr_dRowsByCol[i];
295 #ifdef IDENSITY
296 dst->gcr_iRowsByCol[j] = src->gcr_iRowsByCol[i];
297 #endif /* IDENSITY */
298 }
299
300 /* Now fix up the transform of the new channel */
301 GeoTranslateTrans(&GeoSidewaysTransform, src->gcr_length+1, 0, &t);
302 GeoTransTrans(&t, &src->gcr_transform, &dst->gcr_transform);
303 dst->gcr_origin = src->gcr_origin;
304 dst->gcr_area = src->gcr_area;
305 dst->gcr_type = src->gcr_type;
306 }
307
308 /*
309 * ----------------------------------------------------------------------------
310 *
311 * GCRFlipXY --
312 *
313 * This procedure rotates and flips a channel to interchange
314 * x and y coordinates.
315 *
316 * Results:
317 * None.
318 *
319 * Side effects:
320 * The contents of channel dst are modified so that they are
321 * a x-y flip of src. See comments for GCRFlipLeftRight for
322 * warnings about when it is and isn't safe to call this
323 * procedure.
324 *
325 * ----------------------------------------------------------------------------
326 */
327
328 void
GCRFlipXY(src,dst)329 GCRFlipXY(src, dst)
330 GCRChannel *src; /* Original channel. */
331 GCRChannel *dst; /* Channel to be modified to contain
332 * transformed info from src.
333 */
334 {
335 static Transform flipxy = {0, 1, 0, 1, 0, 0};
336 int tmp, lenWds, widWds;
337 short old, new;
338 int i, j;
339
340 ASSERT(src->gcr_width == dst->gcr_length, "gcrFlipXY: channel mismatch");
341 ASSERT(src->gcr_length == dst->gcr_width, "gcrFlipXY: channel mismatch");
342
343 lenWds = src->gcr_length + 1;
344 widWds = src->gcr_width + 1;
345
346 /* First, flip the side pins to top and bottom */
347 for (i = 0; i <= widWds; i++)
348 {
349 dst->gcr_tPins[i] = src->gcr_rPins[i];
350 tmp = dst->gcr_tPins[i].gcr_x;
351 dst->gcr_tPins[i].gcr_x = dst->gcr_tPins[i].gcr_y;
352 dst->gcr_tPins[i].gcr_y = tmp;
353 dst->gcr_bPins[i] = src->gcr_lPins[i];
354 tmp = dst->gcr_bPins[i].gcr_x;
355 dst->gcr_bPins[i].gcr_x = dst->gcr_bPins[i].gcr_y;
356 dst->gcr_bPins[i].gcr_y = tmp;
357 }
358
359 /* Same thing except flip top and bottom pins to sides */
360 for (i = 0; i <= lenWds; i++)
361 {
362 dst->gcr_rPins[i] = src->gcr_tPins[i];
363 tmp = dst->gcr_rPins[i].gcr_x;
364 dst->gcr_rPins[i].gcr_x = dst->gcr_rPins[i].gcr_y;
365 dst->gcr_rPins[i].gcr_y = tmp;
366 dst->gcr_lPins[i] = src->gcr_bPins[i];
367 tmp = dst->gcr_lPins[i].gcr_x;
368 dst->gcr_lPins[i].gcr_x = dst->gcr_lPins[i].gcr_y;
369 dst->gcr_lPins[i].gcr_y = tmp;
370 }
371
372 /*
373 * Now flip the result array. EXTRA SPECIAL TRICKINESS: the
374 * GCRBLKM and GCRBLKP flags must get switched, because what
375 * blocked a column in the old channel blocks a row in the
376 * new one.
377 */
378 for (i = 0; i <= lenWds; i++)
379 for (j = 0; j <= widWds; j++)
380 {
381 old = src->gcr_result[i][j];
382 new = old & ~(GCRVR|GCRVL|GCRVU|GCRVD|GCRR|GCRU|GCRBLKM|GCRBLKP);
383 if (old & GCRVR) new |= GCRVU;
384 if (old & GCRVU) new |= GCRVR;
385 if (old & GCRVL) new |= GCRVD;
386 if (old & GCRVD) new |= GCRVL;
387 if (old & GCRR) new |= GCRU;
388 if (old & GCRU) new |= GCRR;
389 if (old & GCRBLKM) new |= GCRBLKP;
390 if (old & GCRBLKP) new |= GCRBLKM;
391 dst->gcr_result[j][i] = new;
392 }
393
394 /* Copy the horizontal and vertical density information */
395 dst->gcr_dMaxByRow = src->gcr_dMaxByCol;
396 dst->gcr_dMaxByCol = src->gcr_dMaxByRow;
397 bcopy((char *) src->gcr_dRowsByCol, (char *) dst->gcr_dColsByRow,
398 sizeof (short) * lenWds);
399 bcopy((char *) src->gcr_dColsByRow, (char *) dst->gcr_dRowsByCol,
400 sizeof (short) * widWds);
401 #ifdef IDENSITY
402 bcopy((char *) src->gcr_iRowsByCol, (char *) dst->gcr_iColsByRow,
403 sizeof (short) * lenWds);
404 bcopy((char *) src->gcr_iColsByRow, (char *) dst->gcr_iRowsByCol,
405 sizeof (short) * widWds);
406 #endif /* IDENSITY */
407
408 /* Lastly, make a new transform */
409 GeoTransTrans(&flipxy, &src->gcr_transform, &dst->gcr_transform);
410 dst->gcr_origin = src->gcr_origin;
411 dst->gcr_area = src->gcr_area;
412 switch (src->gcr_type)
413 {
414 case CHAN_HRIVER: dst->gcr_type = CHAN_VRIVER; break;
415 case CHAN_VRIVER: dst->gcr_type = CHAN_HRIVER; break;
416 default: dst->gcr_type = CHAN_NORMAL; break;
417 }
418 }
419
420 /*
421 * ----------------------------------------------------------------------------
422 *
423 * GCRNoFlip --
424 *
425 * This procedure performs the identity transform. It makes a copy.
426 *
427 * Results:
428 * None.
429 *
430 * Side effects:
431 * The contents of channel dst are modified so that they are
432 * a copy of src. Only the four pin arrays, the transform, the
433 * the area, and the result array are modified. The other fields
434 * of dst are untouched. This means,
435 * in particular, that this procedure should be called BEFORE
436 * the linked lists for nets get set up, or else AFTER all the
437 * channel routing has been done and the nets have been freed up.
438 *
439 * ----------------------------------------------------------------------------
440 */
441
442 void
GCRNoFlip(src,dst)443 GCRNoFlip(src, dst)
444 GCRChannel *src; /* Original channel. */
445 GCRChannel *dst; /* Channel to be modified to contain
446 * transformed info from src. The two
447 * channels must have the same dimensions,
448 * but must not be the same channel.
449 */
450 {
451 int lenWds, widWds, pinBytes, resBytes;
452 int i;
453
454 ASSERT(src->gcr_length == dst->gcr_length, "GCRFlipLeftRight: mismatch");
455 ASSERT(src->gcr_width == dst->gcr_width, "GCRFlipLeftRight: mismatch");
456
457 lenWds = src->gcr_length + 1;
458 widWds = src->gcr_width + 1;
459
460 /* Copy pairs of pins in the top and bottom arrays */
461 pinBytes = lenWds * sizeof (GCRPin);
462 bcopy((char *) src->gcr_tPins, (char *) dst->gcr_tPins, pinBytes);
463 bcopy((char *) src->gcr_bPins, (char *) dst->gcr_bPins, pinBytes);
464
465 /* Copy flag values from the result array */
466 resBytes = widWds * sizeof (short);
467 for (i = 0; i <= lenWds; i++)
468 bcopy((char *)src->gcr_result[i], (char *)dst->gcr_result[i], resBytes);
469
470 /* Copy the left and right end pins */
471 pinBytes = widWds * sizeof (GCRPin);
472 bcopy((char *) src->gcr_lPins, (char *) dst->gcr_lPins, pinBytes);
473 bcopy((char *) src->gcr_rPins, (char *) dst->gcr_rPins, pinBytes);
474
475 /* Copy the horizontal and vertical density information */
476 dst->gcr_dMaxByCol = src->gcr_dMaxByCol;
477 dst->gcr_dMaxByRow = src->gcr_dMaxByRow;
478 bcopy((char *) src->gcr_dRowsByCol, (char *) dst->gcr_dRowsByCol,
479 sizeof (short) * lenWds);
480 bcopy((char *) src->gcr_dColsByRow, (char *) dst->gcr_dColsByRow,
481 sizeof (short) * widWds);
482 #ifdef IDENSITY
483 bcopy((char *) src->gcr_iRowsByCol, (char *) dst->gcr_iRowsByCol,
484 sizeof (short) * lenWds);
485 bcopy((char *) src->gcr_iColsByRow, (char *) dst->gcr_iColsByRow,
486 sizeof (short) * widWds);
487 #endif /* IDENSITY */
488
489 /* Now fix up the transform of the new channel */
490 dst->gcr_origin = src->gcr_origin;
491 dst->gcr_transform = src->gcr_transform;
492 dst->gcr_area = src->gcr_area;
493 dst->gcr_type = src->gcr_type;
494 }
495