1 //------------------------------------------------------------------------------
2 // GB_semiring_template.c: built-in unary and binary functions and operators
3 //------------------------------------------------------------------------------
4 
5 // SuiteSparse:GraphBLAS, Timothy A. Davis, (c) 2017-2021, All Rights Reserved.
6 // SPDX-License-Identifier: Apache-2.0
7 
8 //------------------------------------------------------------------------------
9 
10 // This file is #include'd many times in GB_ops.c to define the built-in
11 // semirings.  That file has defined either GB_BOOLEAN, or GB_TYPE as one of
12 // the 10 non-boolean types.
13 
14 // Using built-in types and operators, many unique semirings can be built.
15 // Below is the list of pre-defined semirings in SuiteSparse:GraphBLAS:
16 
17 // 1000 semirings with a multiply operator TxT -> T where T is non-Boolean, from
18 // the complete cross product of:
19 
20 //      5 monoids: MIN, MAX, PLUS, TIMES, ANY
21 //      20 multiply operators:
22 //          FIRST, SECOND, PAIR, MIN, MAX, PLUS, MINUS, RMINUS, TIMES, DIV, RDIV
23 //          ISEQ, ISNE, ISGT, ISLT, ISGE, ISLE,
24 //          LOR, LAND, LXOR
25 //      10 non-Boolean types, T
26 
27 //      a single instance of this file creates 100 semirings of this
28 //      form, of one type T, when T is not BOOL
29 
30 // 300 semirings with a comparison operator TxT -> bool, where T is
31 // non-Boolean, from the complete cross product of:
32 
33 //      5 Boolean monoids: LAND, LOR, LXOR, EQ, ANY
34 //      6 multiply operators: EQ, NE, GT, LT, GE, LE
35 //      10 non-Boolean types, T
36 
37 //      a single instance of this file creates 30 semirings of this form,
38 //      of one type T, when T is not BOOL
39 
40 // 55 semirings with purely Boolean types, bool x bool -> bool, from the
41 // complete cross product of:
42 
43 //      5 Boolean monoids: LAND, LOR, LXOR, EQ, ANY
44 //      11 multiply operators:
45 //          FIRST, SECOND, PAIR, LOR, LAND, LXOR, EQ, GT, LT, GE, LE
46 
47 //      a single instance of this file creates all 5*11 = 55 purely Boolean
48 //      semirings, when T is BOOL and GB_BOOLEAN is defined
49 
50 // 54 complex semirings:
51 
52 //      3 complex monoids: PLUS, TIMES, ANY
53 //      9 multiply operators: FIRST, SECOND, PAIR, PLUS, MINUS, TIMES,
54 //          DIV, RDIV, RMINUS
55 //      2 complex types (FC32 and FC64)
56 
57 // 64 bitwise semirings:
58 
59 //      4 bitwise monoids: BOR, BAND, BXOR, BXNOR
60 //      4 bitwise multiply operators: BOR, BAND, BXOR, BXNOR
61 //      4 unsigned integer types: UINT8, UINT16, UINT32, UINT64
62 
63 // 80 positional semirings:
64 
65 //      5 monoids: MIN, MAX, PLUS, TIMES, ANY
66 //      8 multiply operators:
67 //          FIRSTI, FIRSTI1, FIRSTJ, FIRSTJ1,
68 //          SECONDI, SECONDI1, SECONDJ, SECONDJ1
69 //      2 types: INT32, INT64
70 
71 #if defined ( GB_BOOLEAN )
72 
73     //--------------------------------------------------------------------------
74     // 55 purely Boolean semirings
75     //--------------------------------------------------------------------------
76 
77     // All types in these 44 semirings are BOOL
78 
79     // 11 semirings with LOR monoid; the 2nd argument is the multiply operator
80     GXB_SEMIRING ( LOR   , FIRST  )
81     GXB_SEMIRING ( LOR   , SECOND )
82     GXB_SEMIRING ( LOR   , PAIR   )
83     GXB_SEMIRING ( LOR   , LOR    )
84     GXB_SEMIRING ( LOR   , LAND   )
85     GXB_SEMIRING ( LOR   , LXOR   )
86     GXB_SEMIRING ( LOR   , EQ     )
87     GXB_SEMIRING ( LOR   , GT     )
88     GXB_SEMIRING ( LOR   , LT     )
89     GXB_SEMIRING ( LOR   , GE     )
90     GXB_SEMIRING ( LOR   , LE     )
91 
92     // 11 semirings with LAND monoid; the 2nd argument is the multiply operator
93     GXB_SEMIRING ( LAND  , FIRST  )
94     GXB_SEMIRING ( LAND  , SECOND )
95     GXB_SEMIRING ( LAND  , PAIR   )
96     GXB_SEMIRING ( LAND  , LOR    )
97     GXB_SEMIRING ( LAND  , LAND   )
98     GXB_SEMIRING ( LAND  , LXOR   )
99     GXB_SEMIRING ( LAND  , EQ     )
100     GXB_SEMIRING ( LAND  , GT     )
101     GXB_SEMIRING ( LAND  , LT     )
102     GXB_SEMIRING ( LAND  , GE     )
103     GXB_SEMIRING ( LAND  , LE     )
104 
105     // 11 semirings with LXOR monoid; the 2nd argument is the multiply operator
106     GXB_SEMIRING ( LXOR  , FIRST  )
107     GXB_SEMIRING ( LXOR  , SECOND )
108     GXB_SEMIRING ( LXOR  , PAIR   )
109     GXB_SEMIRING ( LXOR  , LOR    )
110     GXB_SEMIRING ( LXOR  , LAND   )
111     GXB_SEMIRING ( LXOR  , LXOR   )
112     GXB_SEMIRING ( LXOR  , EQ     )
113     GXB_SEMIRING ( LXOR  , GT     )
114     GXB_SEMIRING ( LXOR  , LT     )
115     GXB_SEMIRING ( LXOR  , GE     )
116     GXB_SEMIRING ( LXOR  , LE     )
117 
118     // 11 semirings with EQ monoid; the 2nd argument is the multiply operator
119     GXB_SEMIRING ( EQ    , FIRST  )
120     GXB_SEMIRING ( EQ    , SECOND )
121     GXB_SEMIRING ( EQ    , PAIR   )
122     GXB_SEMIRING ( EQ    , LOR    )
123     GXB_SEMIRING ( EQ    , LAND   )
124     GXB_SEMIRING ( EQ    , LXOR   )
125     GXB_SEMIRING ( EQ    , EQ     )
126     GXB_SEMIRING ( EQ    , GT     )
127     GXB_SEMIRING ( EQ    , LT     )
128     GXB_SEMIRING ( EQ    , GE     )
129     GXB_SEMIRING ( EQ    , LE     )
130 
131     // 11 semirings with ANY monoid; the 2nd argument is the multiply operator
132     GXB_SEMIRING ( ANY   , FIRST  )
133     GXB_SEMIRING ( ANY   , SECOND )
134     GXB_SEMIRING ( ANY   , PAIR   )
135     GXB_SEMIRING ( ANY   , LOR    )
136     GXB_SEMIRING ( ANY   , LAND   )
137     GXB_SEMIRING ( ANY   , LXOR   )
138     GXB_SEMIRING ( ANY   , EQ     )
139     GXB_SEMIRING ( ANY   , GT     )
140     GXB_SEMIRING ( ANY   , LT     )
141     GXB_SEMIRING ( ANY   , GE     )
142     GXB_SEMIRING ( ANY   , LE     )
143 
144 #elif defined ( GB_COMPLEX )
145 
146     //--------------------------------------------------------------------------
147     // 27 complex semirings of the form TxT->t
148     //--------------------------------------------------------------------------
149 
150     // 9 semirings with PLUS monoid
151     GXB_SEMIRING ( PLUS  , FIRST  )
152     GXB_SEMIRING ( PLUS  , SECOND )
153     GXB_SEMIRING ( PLUS  , PAIR   )
154     GXB_SEMIRING ( PLUS  , PLUS   )
155     GXB_SEMIRING ( PLUS  , MINUS  )
156     GXB_SEMIRING ( PLUS  , RMINUS )
157     GXB_SEMIRING ( PLUS  , TIMES  )
158     GXB_SEMIRING ( PLUS  , DIV    )
159     GXB_SEMIRING ( PLUS  , RDIV   )
160 
161     // 9 semirings with TIMES monoid
162     GXB_SEMIRING ( TIMES , FIRST  )
163     GXB_SEMIRING ( TIMES , SECOND )
164     GXB_SEMIRING ( TIMES , PAIR   )
165     GXB_SEMIRING ( TIMES , PLUS   )
166     GXB_SEMIRING ( TIMES , MINUS  )
167     GXB_SEMIRING ( TIMES , RMINUS )
168     GXB_SEMIRING ( TIMES , TIMES  )
169     GXB_SEMIRING ( TIMES , DIV    )
170     GXB_SEMIRING ( TIMES , RDIV   )
171 
172     // 9 semirings with ANY monoid
173     GXB_SEMIRING ( ANY   , FIRST  )
174     GXB_SEMIRING ( ANY   , SECOND )
175     GXB_SEMIRING ( ANY   , PAIR   )
176     GXB_SEMIRING ( ANY   , PLUS   )
177     GXB_SEMIRING ( ANY   , MINUS  )
178     GXB_SEMIRING ( ANY   , RMINUS )
179     GXB_SEMIRING ( ANY   , TIMES  )
180     GXB_SEMIRING ( ANY   , DIV    )
181     GXB_SEMIRING ( ANY   , RDIV   )
182 
183 #else
184 
185     //--------------------------------------------------------------------------
186     // 100 semirings of the form TxT->T
187     //--------------------------------------------------------------------------
188 
189     // All types in these semirings are the same.  These are defined for
190     // the 10 non-Boolean types, not when T is BOOL.
191 
192     // 20 semirings with MIN monoid; the 2nd argument is the multiply operator
193     GXB_SEMIRING ( MIN   , FIRST  )
194     GXB_SEMIRING ( MIN   , SECOND )
195     GXB_SEMIRING ( MIN   , PAIR   )
196     GXB_SEMIRING ( MIN   , MIN    )
197     GXB_SEMIRING ( MIN   , MAX    )
198     GXB_SEMIRING ( MIN   , PLUS   )
199     GXB_SEMIRING ( MIN   , MINUS  )
200     GXB_SEMIRING ( MIN   , RMINUS )
201     GXB_SEMIRING ( MIN   , TIMES  )
202     GXB_SEMIRING ( MIN   , DIV    )
203     GXB_SEMIRING ( MIN   , RDIV   )
204     GXB_SEMIRING ( MIN   , ISEQ   )
205     GXB_SEMIRING ( MIN   , ISNE   )
206     GXB_SEMIRING ( MIN   , ISGT   )
207     GXB_SEMIRING ( MIN   , ISLT   )
208     GXB_SEMIRING ( MIN   , ISGE   )
209     GXB_SEMIRING ( MIN   , ISLE   )
210     GXB_SEMIRING ( MIN   , LOR    )
211     GXB_SEMIRING ( MIN   , LAND   )
212     GXB_SEMIRING ( MIN   , LXOR   )
213 
214     // 20 semirings with MAX monoid; the 2nd argument is the multiply operator
215     GXB_SEMIRING ( MAX   , FIRST  )
216     GXB_SEMIRING ( MAX   , SECOND )
217     GXB_SEMIRING ( MAX   , PAIR   )
218     GXB_SEMIRING ( MAX   , MIN    )
219     GXB_SEMIRING ( MAX   , MAX    )
220     GXB_SEMIRING ( MAX   , PLUS   )
221     GXB_SEMIRING ( MAX   , MINUS  )
222     GXB_SEMIRING ( MAX   , RMINUS )
223     GXB_SEMIRING ( MAX   , TIMES  )
224     GXB_SEMIRING ( MAX   , DIV    )
225     GXB_SEMIRING ( MAX   , RDIV   )
226     GXB_SEMIRING ( MAX   , ISEQ   )
227     GXB_SEMIRING ( MAX   , ISNE   )
228     GXB_SEMIRING ( MAX   , ISGT   )
229     GXB_SEMIRING ( MAX   , ISLT   )
230     GXB_SEMIRING ( MAX   , ISGE   )
231     GXB_SEMIRING ( MAX   , ISLE   )
232     GXB_SEMIRING ( MAX   , LOR    )
233     GXB_SEMIRING ( MAX   , LAND   )
234     GXB_SEMIRING ( MAX   , LXOR   )
235 
236     // 20 semirings with PLUS monoid; the 2nd argument is the multiply operator
237     GXB_SEMIRING ( PLUS  , FIRST  )
238     GXB_SEMIRING ( PLUS  , SECOND )
239     GXB_SEMIRING ( PLUS  , PAIR   )
240     GXB_SEMIRING ( PLUS  , MIN    )
241     GXB_SEMIRING ( PLUS  , MAX    )
242     GXB_SEMIRING ( PLUS  , PLUS   )
243     GXB_SEMIRING ( PLUS  , MINUS  )
244     GXB_SEMIRING ( PLUS  , RMINUS )
245     GXB_SEMIRING ( PLUS  , TIMES  )
246     GXB_SEMIRING ( PLUS  , DIV    )
247     GXB_SEMIRING ( PLUS  , RDIV   )
248     GXB_SEMIRING ( PLUS  , ISEQ   )
249     GXB_SEMIRING ( PLUS  , ISNE   )
250     GXB_SEMIRING ( PLUS  , ISGT   )
251     GXB_SEMIRING ( PLUS  , ISLT   )
252     GXB_SEMIRING ( PLUS  , ISGE   )
253     GXB_SEMIRING ( PLUS  , ISLE   )
254     GXB_SEMIRING ( PLUS  , LOR    )
255     GXB_SEMIRING ( PLUS  , LAND   )
256     GXB_SEMIRING ( PLUS  , LXOR   )
257 
258     // 20 semirings with TIMES monoid; the 2nd argument is the multiply operator
259     GXB_SEMIRING ( TIMES , FIRST  )
260     GXB_SEMIRING ( TIMES , SECOND )
261     GXB_SEMIRING ( TIMES , PAIR   )
262     GXB_SEMIRING ( TIMES , MIN    )
263     GXB_SEMIRING ( TIMES , MAX    )
264     GXB_SEMIRING ( TIMES , PLUS   )
265     GXB_SEMIRING ( TIMES , MINUS  )
266     GXB_SEMIRING ( TIMES , RMINUS )
267     GXB_SEMIRING ( TIMES , TIMES  )
268     GXB_SEMIRING ( TIMES , DIV    )
269     GXB_SEMIRING ( TIMES , RDIV   )
270     GXB_SEMIRING ( TIMES , ISEQ   )
271     GXB_SEMIRING ( TIMES , ISNE   )
272     GXB_SEMIRING ( TIMES , ISGT   )
273     GXB_SEMIRING ( TIMES , ISLT   )
274     GXB_SEMIRING ( TIMES , ISGE   )
275     GXB_SEMIRING ( TIMES , ISLE   )
276     GXB_SEMIRING ( TIMES , LOR    )
277     GXB_SEMIRING ( TIMES , LAND   )
278     GXB_SEMIRING ( TIMES , LXOR   )
279 
280     // 20 semirings with ANY monoid; the 2nd argument is the multiply operator
281     GXB_SEMIRING ( ANY   , FIRST  )
282     GXB_SEMIRING ( ANY   , SECOND )
283     GXB_SEMIRING ( ANY   , PAIR   )
284     GXB_SEMIRING ( ANY   , MIN    )
285     GXB_SEMIRING ( ANY   , MAX    )
286     GXB_SEMIRING ( ANY   , PLUS   )
287     GXB_SEMIRING ( ANY   , MINUS  )
288     GXB_SEMIRING ( ANY   , RMINUS )
289     GXB_SEMIRING ( ANY   , TIMES  )
290     GXB_SEMIRING ( ANY   , DIV    )
291     GXB_SEMIRING ( ANY   , RDIV   )
292     GXB_SEMIRING ( ANY   , ISEQ   )
293     GXB_SEMIRING ( ANY   , ISNE   )
294     GXB_SEMIRING ( ANY   , ISGT   )
295     GXB_SEMIRING ( ANY   , ISLT   )
296     GXB_SEMIRING ( ANY   , ISGE   )
297     GXB_SEMIRING ( ANY   , ISLE   )
298     GXB_SEMIRING ( ANY   , LOR    )
299     GXB_SEMIRING ( ANY   , LAND   )
300     GXB_SEMIRING ( ANY   , LXOR   )
301 
302     //--------------------------------------------------------------------------
303     // 30 semirings of the form TxT -> bool
304     //--------------------------------------------------------------------------
305 
306     // The multiply operator has the form z=compare(x,y), where x and y are of
307     // type T, and z is Boolean.  These operators are combined with the four
308     // Boolean monoids.
309 
310     // These are defined when T is one of the 10 non-Boolean types, not when T
311     // is BOOL
312 
313     // 6 semrings with LOR monoid; the 2nd argument is the comparison operator
314     GXB_SEMIRING_COMPARE ( LOR  , EQ )
315     GXB_SEMIRING_COMPARE ( LOR  , NE )
316     GXB_SEMIRING_COMPARE ( LOR  , GT )
317     GXB_SEMIRING_COMPARE ( LOR  , LT )
318     GXB_SEMIRING_COMPARE ( LOR  , GE )
319     GXB_SEMIRING_COMPARE ( LOR  , LE )
320 
321     // 6 semrings with LAND monoid; the 2nd argument is the comparison operator
322     GXB_SEMIRING_COMPARE ( LAND , EQ )
323     GXB_SEMIRING_COMPARE ( LAND , NE )
324     GXB_SEMIRING_COMPARE ( LAND , GT )
325     GXB_SEMIRING_COMPARE ( LAND , LT )
326     GXB_SEMIRING_COMPARE ( LAND , GE )
327     GXB_SEMIRING_COMPARE ( LAND , LE )
328 
329     // 6 semrings with LXOR monoid; the 2nd argument is the comparison operator
330     GXB_SEMIRING_COMPARE ( LXOR , EQ )
331     GXB_SEMIRING_COMPARE ( LXOR , NE )
332     GXB_SEMIRING_COMPARE ( LXOR , GT )
333     GXB_SEMIRING_COMPARE ( LXOR , LT )
334     GXB_SEMIRING_COMPARE ( LXOR , GE )
335     GXB_SEMIRING_COMPARE ( LXOR , LE )
336 
337     // 6 semrings with EQ monoid; the 2nd argument is the comparison operator
338     GXB_SEMIRING_COMPARE ( EQ   , EQ )
339     GXB_SEMIRING_COMPARE ( EQ   , NE )
340     GXB_SEMIRING_COMPARE ( EQ   , GT )
341     GXB_SEMIRING_COMPARE ( EQ   , LT )
342     GXB_SEMIRING_COMPARE ( EQ   , GE )
343     GXB_SEMIRING_COMPARE ( EQ   , LE )
344 
345     // 6 semrings with ANY monoid; the 2nd argument is the comparison operator
346     GXB_SEMIRING_COMPARE ( ANY  , EQ )
347     GXB_SEMIRING_COMPARE ( ANY  , NE )
348     GXB_SEMIRING_COMPARE ( ANY  , GT )
349     GXB_SEMIRING_COMPARE ( ANY  , LT )
350     GXB_SEMIRING_COMPARE ( ANY  , GE )
351     GXB_SEMIRING_COMPARE ( ANY  , LE )
352 
353 #endif
354 
355 #if defined ( GB_UNSIGNED_INT )
356 
357     //--------------------------------------------------------------------------
358     // 16 bitwise semirings (for unsigned integers only)
359     //--------------------------------------------------------------------------
360 
361     GXB_SEMIRING ( BOR   , BOR    )
362     GXB_SEMIRING ( BOR   , BAND   )
363     GXB_SEMIRING ( BOR   , BXOR   )
364     GXB_SEMIRING ( BOR   , BXNOR  )
365 
366     GXB_SEMIRING ( BAND  , BOR    )
367     GXB_SEMIRING ( BAND  , BAND   )
368     GXB_SEMIRING ( BAND  , BXOR   )
369     GXB_SEMIRING ( BAND  , BXNOR  )
370 
371     GXB_SEMIRING ( BXOR  , BOR    )
372     GXB_SEMIRING ( BXOR  , BAND   )
373     GXB_SEMIRING ( BXOR  , BXOR   )
374     GXB_SEMIRING ( BXOR  , BXNOR  )
375 
376     GXB_SEMIRING ( BXNOR , BOR    )
377     GXB_SEMIRING ( BXNOR , BAND   )
378     GXB_SEMIRING ( BXNOR , BXOR   )
379     GXB_SEMIRING ( BXNOR , BXNOR  )
380 
381 #endif
382 
383 #if defined ( GB_POSITIONAL )
384 
385     //--------------------------------------------------------------------------
386     // 40 positional semirings:
387     //--------------------------------------------------------------------------
388 
389     GXB_SEMIRING ( MIN   , FIRSTI   )
390     GXB_SEMIRING ( MIN   , FIRSTI1  )
391     GXB_SEMIRING ( MIN   , FIRSTJ   )
392     GXB_SEMIRING ( MIN   , FIRSTJ1  )
393     GXB_SEMIRING ( MIN   , SECONDI  )
394     GXB_SEMIRING ( MIN   , SECONDI1 )
395     GXB_SEMIRING ( MIN   , SECONDJ  )
396     GXB_SEMIRING ( MIN   , SECONDJ1 )
397 
398     GXB_SEMIRING ( MAX   , FIRSTI   )
399     GXB_SEMIRING ( MAX   , FIRSTI1  )
400     GXB_SEMIRING ( MAX   , FIRSTJ   )
401     GXB_SEMIRING ( MAX   , FIRSTJ1  )
402     GXB_SEMIRING ( MAX   , SECONDI  )
403     GXB_SEMIRING ( MAX   , SECONDI1 )
404     GXB_SEMIRING ( MAX   , SECONDJ  )
405     GXB_SEMIRING ( MAX   , SECONDJ1 )
406 
407     GXB_SEMIRING ( ANY   , FIRSTI   )
408     GXB_SEMIRING ( ANY   , FIRSTI1  )
409     GXB_SEMIRING ( ANY   , FIRSTJ   )
410     GXB_SEMIRING ( ANY   , FIRSTJ1  )
411     GXB_SEMIRING ( ANY   , SECONDI  )
412     GXB_SEMIRING ( ANY   , SECONDI1 )
413     GXB_SEMIRING ( ANY   , SECONDJ  )
414     GXB_SEMIRING ( ANY   , SECONDJ1 )
415 
416     GXB_SEMIRING ( PLUS  , FIRSTI   )
417     GXB_SEMIRING ( PLUS  , FIRSTI1  )
418     GXB_SEMIRING ( PLUS  , FIRSTJ   )
419     GXB_SEMIRING ( PLUS  , FIRSTJ1  )
420     GXB_SEMIRING ( PLUS  , SECONDI  )
421     GXB_SEMIRING ( PLUS  , SECONDI1 )
422     GXB_SEMIRING ( PLUS  , SECONDJ  )
423     GXB_SEMIRING ( PLUS  , SECONDJ1 )
424 
425     GXB_SEMIRING ( TIMES , FIRSTI   )
426     GXB_SEMIRING ( TIMES , FIRSTI1  )
427     GXB_SEMIRING ( TIMES , FIRSTJ   )
428     GXB_SEMIRING ( TIMES , FIRSTJ1  )
429     GXB_SEMIRING ( TIMES , SECONDI  )
430     GXB_SEMIRING ( TIMES , SECONDI1 )
431     GXB_SEMIRING ( TIMES , SECONDJ  )
432     GXB_SEMIRING ( TIMES , SECONDJ1 )
433 
434 #endif
435 
436 #undef GB_XTYPE
437 #undef GB_BOOLEAN
438 #undef GB_COMPLEX
439 #undef GB_UNSIGNED_INT
440 #undef GB_POSITIONAL
441 
442