Fix assertion for proper Huffman merge pattern: 0 == 1 modulo 1.
[pspp] / src / flip.c
1 /* PSPP - computes sample statistics.
2    Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3    Written by Ben Pfaff <blp@gnu.org>.
4
5    This program is free software; you can redistribute it and/or
6    modify it under the terms of the GNU General Public License as
7    published by the Free Software Foundation; either version 2 of the
8    License, or (at your option) any later version.
9
10    This program is distributed in the hope that it will be useful, but
11    WITHOUT ANY WARRANTY; without even the implied warranty of
12    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13    General Public License for more details.
14
15    You should have received a copy of the GNU General Public License
16    along with this program; if not, write to the Free Software
17    Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
18    02111-1307, USA. */
19
20 #include <config.h>
21 #include "error.h"
22 #include <ctype.h>
23 #include <errno.h>
24 #include <float.h>
25 #include <limits.h>
26 #include <stdlib.h>
27 #ifdef HAVE_SYS_TYPES_H
28 #include <sys/types.h>
29 #endif
30 #include "alloc.h"
31 #include "case.h"
32 #include "command.h"
33 #include "dictionary.h"
34 #include "error.h"
35 #include "lexer.h"
36 #include "misc.h"
37 #include "settings.h"
38 #include "str.h"
39 #include "var.h"
40 #include "vfm.h"
41
42 /* List of variable names. */
43 struct varname
44   {
45     struct varname *next;
46     char name[9];
47   };
48
49 /* Represents a FLIP input program. */
50 struct flip_pgm 
51   {
52     struct variable **var;      /* Variables to transpose. */
53     int var_cnt;                /* Number of elements in `var'. */
54     int case_cnt;               /* Pre-flip case count. */
55     size_t case_size;           /* Post-flip bytes per case. */
56
57     struct variable *new_names; /* Variable containing new variable names. */
58     struct varname *new_names_head; /* First new variable. */
59     struct varname *new_names_tail; /* Last new variable. */
60
61     FILE *file;                 /* Temporary file containing data. */
62   };
63
64 static void destroy_flip_pgm (struct flip_pgm *);
65 static struct case_sink *flip_sink_create (struct flip_pgm *);
66 static struct case_source *flip_source_create (struct flip_pgm *);
67 static void flip_file (struct flip_pgm *);
68 static int build_dictionary (struct flip_pgm *);
69
70 static const struct case_source_class flip_source_class;
71 static const struct case_sink_class flip_sink_class;
72
73 /* Parses and executes FLIP. */
74 int
75 cmd_flip (void)
76 {
77   struct flip_pgm *flip;
78
79   if (temporary != 0)
80     {
81       msg (SM, _("FLIP ignores TEMPORARY.  "
82                  "Temporary transformations will be made permanent."));
83       cancel_temporary (); 
84     }
85
86   flip = xmalloc (sizeof *flip);
87   flip->var = NULL;
88   flip->var_cnt = 0;
89   flip->case_cnt = 0;
90   flip->new_names = NULL;
91   flip->new_names_head = NULL;
92   flip->new_names_tail = NULL;
93   flip->file = NULL;
94
95   lex_match ('/');
96   if (lex_match_id ("VARIABLES"))
97     {
98       lex_match ('=');
99       if (!parse_variables (default_dict, &flip->var, &flip->var_cnt, PV_NO_DUPLICATE))
100         return CMD_FAILURE;
101       lex_match ('/');
102     }
103   else
104     dict_get_vars (default_dict, &flip->var, &flip->var_cnt, 1u << DC_SYSTEM);
105
106   lex_match ('/');
107   if (lex_match_id ("NEWNAMES"))
108     {
109       lex_match ('=');
110       flip->new_names = parse_variable ();
111       if (!flip->new_names)
112         goto error;
113     }
114   else
115     flip->new_names = dict_lookup_var (default_dict, "CASE_LBL");
116
117   if (flip->new_names)
118     {
119       int i;
120       
121       for (i = 0; i < flip->var_cnt; i++)
122         if (flip->var[i] == flip->new_names)
123           {
124             memmove (&flip->var[i], &flip->var[i + 1], sizeof *flip->var * (flip->var_cnt - i - 1));
125             flip->var_cnt--;
126             break;
127           }
128     }
129
130   /* Read the active file into a flip_sink. */
131   flip->case_cnt = 0;
132   temp_trns = temporary = 0;
133   vfm_sink = flip_sink_create (flip);
134   flip->new_names_tail = NULL;
135   procedure (NULL, NULL);
136
137   /* Flip the data we read. */
138   flip_file (flip);
139
140   /* Flip the dictionary. */
141   dict_clear (default_dict);
142   if (!build_dictionary (flip))
143     {
144       discard_variables ();
145       goto error;
146     }
147   flip->case_size = dict_get_case_size (default_dict);
148
149   /* Set up flipped data for reading. */
150   vfm_source = flip_source_create (flip);
151
152   return lex_end_of_command ();
153
154  error:
155   destroy_flip_pgm (flip);
156   return CMD_FAILURE;
157 }
158
159 /* Destroys FLIP. */
160 static void
161 destroy_flip_pgm (struct flip_pgm *flip) 
162 {
163   struct varname *iter, *next;
164   
165   free (flip->var);
166   for (iter = flip->new_names_head; iter != NULL; iter = next) 
167     {
168       next = iter->next;
169       free (iter);
170     }
171   if (flip->file != NULL)
172     fclose (flip->file);
173   free (flip);
174 }
175
176 /* Make a new variable with base name NAME, which is bowdlerized and
177    mangled until acceptable, and returns success. */
178 static int
179 make_new_var (char name[])
180 {
181   /* Fix invalid characters. */
182   {
183     char *cp;
184   
185     for (cp = name; *cp && !isspace (*cp); cp++)
186       {
187         *cp = toupper ((unsigned char) *cp);
188         if (!isalpha (*cp) && *cp != '@' && *cp != '#'
189             && (cp == name || (*cp != '.' && *cp != '$' && *cp != '_'
190                                && !isdigit (*cp))))
191           {
192             if (cp == name)
193               *cp = 'V';        /* _ not valid in first position. */
194             else
195               *cp = '_';
196           }
197       }
198     *cp = 0;
199   }
200   
201   if (dict_create_var (default_dict, name, 0))
202     return 1;
203
204   /* Add numeric extensions until acceptable. */
205   {
206     int len = (int) strlen (name);
207     char n[9];
208     int i;
209
210     for (i = 1; i < 10000000; i++)
211       {
212         int ofs = min (7 - intlog10 (i), len);
213         memcpy (n, name, ofs);
214         sprintf (&n[ofs], "%d", i);
215
216         if (dict_create_var (default_dict, n, 0))
217           return 1;
218       }
219   }
220
221   msg (SE, _("Could not create acceptable variant for variable %s."), name);
222   return 0;
223 }
224
225 /* Make a new dictionary for all the new variable names. */
226 static int
227 build_dictionary (struct flip_pgm *flip)
228 {
229   dict_create_var_assert (default_dict, "CASE_LBL", 8);
230
231   if (flip->new_names_head == NULL)
232     {
233       int i;
234       
235       if (flip->case_cnt > 99999)
236         {
237           msg (SE, _("Cannot create more than 99999 variable names."));
238           return 0;
239         }
240       
241       for (i = 0; i < flip->case_cnt; i++)
242         {
243           struct variable *v;
244           char s[9];
245
246           sprintf (s, "VAR%03d", i);
247           v = dict_create_var_assert (default_dict, s, 0);
248         }
249     }
250   else
251     {
252       struct varname *v;
253
254       for (v = flip->new_names_head; v; v = v->next)
255         if (!make_new_var (v->name))
256           return 0;
257     }
258   
259   return 1;
260 }
261      
262 /* Cases during transposition. */
263 struct flip_sink_info 
264   {
265     struct flip_pgm *flip;              /* FLIP program. */
266     union value *output_buf;            /* Case output buffer. */
267   };
268
269 /* Creates a flip sink based on FLIP. */
270 static struct case_sink *
271 flip_sink_create (struct flip_pgm *flip) 
272 {
273   struct flip_sink_info *info = xmalloc (sizeof *info);
274   int i;
275
276   info->flip = flip;
277   info->output_buf = xmalloc (sizeof *info->output_buf * flip->var_cnt);
278
279   flip->file = tmpfile ();
280   if (!flip->file)
281     msg (FE, _("Could not create temporary file for FLIP."));
282
283   /* Write variable names as first case. */
284   for (i = 0; i < flip->var_cnt; i++) 
285     st_bare_pad_copy (info->output_buf[i].s, flip->var[i]->name, 8);
286   if (fwrite (info->output_buf, sizeof *info->output_buf,
287               flip->var_cnt, flip->file) != (size_t) flip->var_cnt)
288     msg (FE, _("Error writing FLIP file: %s."), strerror (errno));
289
290   flip->case_cnt = 1;
291
292   return create_case_sink (&flip_sink_class, default_dict, info);
293 }
294
295 /* Writes case C to the FLIP sink. */
296 static void
297 flip_sink_write (struct case_sink *sink, const struct ccase *c)
298 {
299   struct flip_sink_info *info = sink->aux;
300   struct flip_pgm *flip = info->flip;
301   int i;
302   
303   flip->case_cnt++;
304
305   if (flip->new_names != NULL)
306     {
307       struct varname *v = xmalloc (sizeof (struct varname));
308       v->next = NULL;
309       if (flip->new_names->type == NUMERIC) 
310         {
311           double f = case_num (c, sink->idx_to_fv[flip->new_names->index]);
312
313           if (f == SYSMIS)
314             strcpy (v->name, "VSYSMIS");
315           else if (f < INT_MIN)
316             strcpy (v->name, "VNEGINF");
317           else if (f > INT_MAX)
318             strcpy (v->name, "VPOSINF");
319           else 
320             {
321               char name[INT_DIGITS + 2];
322               sprintf (name, "V%d", (int) f);
323               strncpy (v->name, name, 8);
324               name[8] = 0; 
325             }
326         }
327       else
328         {
329           int width = min (flip->new_names->width, 8);
330           memcpy (v->name, case_str (c, sink->idx_to_fv[flip->new_names->index]),
331                   width);
332           v->name[width] = 0;
333         }
334       
335       if (flip->new_names_head == NULL)
336         flip->new_names_head = v;
337       else
338         flip->new_names_tail->next = v;
339       flip->new_names_tail = v;
340     }
341
342   /* Write to external file. */
343   for (i = 0; i < flip->var_cnt; i++)
344     {
345       double out;
346       
347       if (flip->var[i]->type == NUMERIC)
348         out = case_num (c, sink->idx_to_fv[flip->var[i]->index]);
349       else
350         out = SYSMIS;
351       info->output_buf[i].f = out;
352     }
353           
354   if (fwrite (info->output_buf, sizeof *info->output_buf,
355               flip->var_cnt, flip->file) != (size_t) flip->var_cnt)
356     msg (FE, _("Error writing FLIP file: %s."), strerror (errno));
357 }
358
359 /* Transposes the external file into a new file. */
360 static void
361 flip_file (struct flip_pgm *flip)
362 {
363   size_t case_bytes;
364   size_t case_capacity;
365   size_t case_idx;
366   union value *input_buf, *output_buf;
367   FILE *input_file, *output_file;
368
369   /* Allocate memory for many cases. */
370   case_bytes = flip->var_cnt * sizeof *input_buf;
371   case_capacity = get_max_workspace() / case_bytes;
372   if (case_capacity > flip->case_cnt * 2)
373     case_capacity = flip->case_cnt * 2;
374   if (case_capacity < 2)
375     case_capacity = 2;
376   for (;;)
377     {
378       size_t bytes = case_bytes * case_capacity;
379       if (case_capacity > 2)
380         input_buf = malloc (bytes);
381       else
382         input_buf = xmalloc (bytes);
383       if (input_buf != NULL)
384         break;
385
386       case_capacity /= 2;
387       if (case_capacity < 2)
388         case_capacity = 2;
389     }
390
391   /* Use half the allocated memory for input_buf, half for
392      output_buf. */
393   case_capacity /= 2;
394   output_buf = input_buf + flip->var_cnt * case_capacity;
395
396   input_file = flip->file;
397   if (fseek (input_file, 0, SEEK_SET) != 0)
398     msg (FE, _("Error rewinding FLIP file: %s."), strerror (errno));
399
400   output_file = tmpfile ();
401   if (output_file == NULL)
402     msg (FE, _("Error creating FLIP source file."));
403   
404   for (case_idx = 0; case_idx < flip->case_cnt; )
405     {
406       unsigned long read_cases = min (flip->case_cnt - case_idx,
407                                       case_capacity);
408       int i;
409
410       if (read_cases != fread (input_buf, case_bytes, read_cases, input_file))
411         msg (FE, _("Error reading FLIP file: %s."), strerror (errno));
412
413       for (i = 0; i < flip->var_cnt; i++)
414         {
415           unsigned long j;
416           
417           for (j = 0; j < read_cases; j++)
418             output_buf[j] = input_buf[i + j * flip->var_cnt];
419
420 #ifndef HAVE_FSEEKO
421 #define fseeko fseek
422 #endif
423
424 #ifndef HAVE_OFF_T
425 #define off_t long int
426 #endif
427
428           if (fseeko (output_file,
429                       sizeof *input_buf * (case_idx
430                                            + (off_t) i * flip->case_cnt),
431                       SEEK_SET) != 0)
432             msg (FE, _("Error seeking FLIP source file: %s."),
433                        strerror (errno));
434
435           if (fwrite (output_buf, sizeof *output_buf, read_cases, output_file)
436               != read_cases)
437             msg (FE, _("Error writing FLIP source file: %s."),
438                  strerror (errno));
439         }
440
441       case_idx += read_cases;
442     }
443
444   fclose (input_file);
445   free (input_buf);
446   
447   if (fseek (output_file, 0, SEEK_SET) != 0)
448     msg (FE, _("Error rewind FLIP source file: %s."), strerror (errno));
449   flip->file = output_file;
450 }
451
452 /* Destroy sink's internal data. */
453 static void
454 flip_sink_destroy (struct case_sink *sink)
455 {
456   struct flip_sink_info *info = sink->aux;
457
458   free (info->output_buf);
459   free (info);
460 }
461
462 /* FLIP sink class. */
463 static const struct case_sink_class flip_sink_class = 
464   {
465     "FLIP",
466     NULL,
467     flip_sink_write,
468     flip_sink_destroy,
469     NULL,
470   };
471
472 /* Creates and returns a FLIP source based on PGM,
473    which should have already been used as a sink. */
474 static struct case_source *
475 flip_source_create (struct flip_pgm *pgm)
476 {
477   return create_case_source (&flip_source_class, default_dict, pgm);
478 }
479
480 /* Reads the FLIP stream.  Copies each case into C and calls
481    WRITE_CASE passing WC_DATA. */
482 static void
483 flip_source_read (struct case_source *source,
484                   struct ccase *c,
485                   write_case_func *write_case, write_case_data wc_data)
486 {
487   struct flip_pgm *flip = source->aux;
488   union value *input_buf;
489   int i;
490
491   input_buf = xmalloc (sizeof *input_buf * flip->case_cnt);
492   for (i = 0; i < flip->var_cnt; i++)
493     {
494       size_t j;
495       
496       if (fread (input_buf, sizeof *input_buf, flip->case_cnt,
497                  flip->file) != flip->case_cnt) 
498         {
499           if (ferror (flip->file))
500             msg (SE, _("Error reading FLIP temporary file: %s."),
501                  strerror (errno));
502           else if (feof (flip->file))
503             msg (SE, _("Unexpected end of file reading FLIP temporary file."));
504           else
505             assert (0);
506           break;
507         }
508
509       for (j = 0; j < flip->case_cnt; j++)
510         case_data_rw (c, j)->f = input_buf[j].f;
511       if (!write_case (wc_data))
512         break;
513     }
514   free (input_buf);
515 }
516
517 /* Destroy internal data in SOURCE. */
518 static void
519 flip_source_destroy (struct case_source *source)
520 {
521   struct flip_pgm *flip = source->aux;
522
523   destroy_flip_pgm (flip);
524 }
525
526 static const struct case_source_class flip_source_class = 
527   {
528     "FLIP",
529     NULL,
530     flip_source_read,
531     flip_source_destroy
532   };