-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathmod.h
157 lines (152 loc) · 3.09 KB
/
mod.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
#ifndef _MOD_H
#define _MOD_H
#ifndef WIN32
#define DEFINEDWIN32
#define WIN32
#endif
#ifndef WIN32
/*
#define modasm1(ll, p, r) \
{ \
r = static_cast<long int>(ll % p); \
if (r < 0) r += p; \
}
*/
#define modasm1(ll, p, r) \
{ \
long int a = ll >> 32; \
unsigned long int b = (unsigned long int)(ll & 0xffffffffLL); \
asm( \
"xorl %%eax, %%eax\n\t" \
"movl $1, %%edx\n\t" \
"divl %[" #p "]\n\t" \
"movl %%edx, %%eax\n\t" \
"imull %[a]\n\t" \
"addl %[b], %%eax\n\t" \
"adcl $0, %%edx\n\t" \
"idivl %[" #p "]\n\t" \
"testl %%edx, %%edx\n\t" \
"jns 1f\n\t" \
"addl %[" #p "], %%edx\n" \
"1:\n\t" \
"movl %%edx, %[" #r "]" \
: [r] "=&r" (r) \
: [p] "r" (p), [a] "r" (a), [b] "r" (b) \
: "dx", "ax"); \
}
#else
#define modasm1(ll, p, r) \
{ \
r = static_cast<long int>(ll % p); \
if (r < 0) r += p; \
}
#endif
#ifndef WIN32
#define modasm2(ll, p, r) \
long int r; \
{ \
long int a = ll >> 32; \
unsigned long int b = (unsigned long int)(ll & 0xffffffffLL); \
if (a >= p || p < 100L) \
{ \
asm( \
"xorl %%eax, %%eax\n\t" \
"movl $1, %%edx\n\t" \
"divl %[" #p "]\n\t" \
"movl %%edx, %%eax\n\t" \
"imull %[a]\n\t" \
"addl %[b], %%eax\n\t" \
"adcl $0, %%edx\n\t" \
"divl %[" #p "]\n\t" \
"movl %%edx, %[" #r "]" \
: [r] "=&r" (r) \
: [p] "r" (p), [a] "r" (a), [b] "r" (b) \
: "dx", "ax"); \
} \
else \
{ \
asm( \
"divl %[" #p "]\n\t" \
: [r] "=&d" (r) \
: [p] "r" (p), [a] "0" (a), [b] "a" (b) ); \
} \
}
#else
#define modasm2(ll, p, r) \
long int r; \
{ \
r = static_cast<long int>(ll % p); \
if (r < 0) r += p; \
}
#endif
inline long int modasm(long long int ll, long int p)
{
long int r;
modasm1(ll, p, r);
return r;
}
#ifndef WIN32
#define mulmodasm1(l1, l2, p, r) \
long int r; \
{ \
asm( \
"imul %[" #l1 "]\n\t" \
"idivl %[" #p "]\n\t" \
: [r] "=&d" (r) \
: [l1] "r" (l1), [l2] "a" (l2), [p] "r" (p) ); \
}
#else
#define mulmodasm1(l1, l2, p, r) \
long int r; \
{ \
r = ((long long)l1 * l2) % p; \
}
#endif
#ifndef WIN32
#define mulmodasm2(l1, l2, p, r) \
{ \
asm( \
"imul %[" #l1 "]\n\t" \
"idivl %[" #p "]\n\t" \
"testl %%edx, %%edx\n\t" \
"jns 1f\n\t" \
"addl %[" #p "], %%edx\n" \
"1:\n\t" \
: [r] "=&d" (r) \
: [l1] "r" (l1), [l2] "a" (l2), [p] "r" (p) ); \
}
#else
#define mulmodasm2(l1, l2, p, r) \
{ \
r = static_cast<long int>(((long long)l1 * l2) % p); \
if (r < 0) r += p; \
}
#endif
#ifndef WIN32
#define mulmodasm3(l1, l2, p, r) \
long int r; \
{ \
asm( \
"imul %[" #l1 "]\n\t" \
"idivl %[" #p "]\n\t" \
: [r] "=&d" (r), [l2] "=&a" (l2) \
: [l1] "r" (l1), [p] "r" (p) ); \
}
#else
#define mulmodasm3(l1, l2, p, r) \
long int r; \
{ \
r = ((long long)l1 * l2) % p; \
l2 = ((long long)l1 * l2) / p; \
}
#endif
inline long int mulmodasm(long int l1, long int l2, long int p)
{
long int r;
mulmodasm2(l1, l2, p, r);
return r;
}
#ifdef DEFINEDWIN32
#undef WIN32
#endif
#endif