// uses https://github.com/martinus/robin-hood-hashing
// clang++ -std=c++17 -o w w.cc -W -Wall -Wextra -Wshadow -g -O3 -flto -lpthread -fuse-ld=lld

#include <iostream>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <string_view>
#include "robin_hood.h"
#include <algorithm>
#include <thread>
#include <future>

#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#include <fcntl.h>
#include <sys/mman.h>

#include <xmmintrin.h>
#include <smmintrin.h>

using namespace std;

static bool isspace(char c) {
  return (c == ' ' || c=='\n' || c=='\t' || c=='\r');
}

#ifdef __SSE__

#ifndef __SSE4_2__
// Unfortunately, using _mm_set1_epi8 in the loop will cause 4 loads.
// The whole reason why we do this is so we can save loads.
// So we cheat and declare explicit register variables that we will
// initialize outside the call to l2. This disgusting hack will confuse
// g++ 8.3 enough that it generates invalid assembler code.  clang++ 9
// works.
__m128i _space asm ("%xmm7");
__m128i _nl asm ("%xmm6");
__m128i _cr asm ("%xmm5");
__m128i _tab asm ("%xmm4");
#else
__m128i mask asm("%xmm7");
#endif

size_t l2(const char* s) {
  for (size_t r=0; ; r+=sizeof(__m128i)) {
    __m128i v=_mm_loadu_si128((__m128i*)(s+r));
#ifdef __SSE4_2__

    unsigned int x = _mm_cmpistri(mask,v,
	_SIDD_UBYTE_OPS|_SIDD_CMP_EQUAL_ANY|_SIDD_POSITIVE_POLARITY|_SIDD_LEAST_SIGNIFICANT);

    if (x < 16)
      return r + x;

#else

#if 0
    // the version we really wanted:
    uint32_t x = _mm_movemask_epi8(
	_mm_or_si128(
	  _mm_or_si128(_mm_cmpeq_epi8(v,_mm_set1_epi8(0x20)),_mm_cmpeq_epi8(v,_mm_set1_epi8(0x0a))),
	  _mm_or_si128(_mm_cmpeq_epi8(v,_mm_set1_epi8(0x0d)),_mm_cmpeq_epi8(v,_mm_set1_epi8(0x09))))
	);
#else
    // this code does an unsigned load of a 16-byte vector,
    // then does four element-wise vector compares, ORing the results
    // finally converts each byte into a bit in x and calls
    // __builtin_ffs to get gcc to generate a bit-scan instruction.
    uint32_t x = _mm_movemask_epi8(
	_mm_or_si128(
	  _mm_or_si128(_mm_cmpeq_epi8(v,_space),_mm_cmpeq_epi8(v,_nl)),
	  _mm_or_si128(_mm_cmpeq_epi8(v,_cr),_mm_cmpeq_epi8(v,_tab)))
	);
#endif		// #if 0

    if (x)
      return r + __builtin_ffs(x) - 1;

#endif		// #ifdef __SSE4_2__

  }
}
#endif		// #ifdef __SSE__

void tokenize(string_view sv,robin_hood::unordered_map<string_view, int>* m) {
  size_t n=sv.size(),a,b;
#ifdef __SSE__
#ifdef __SSE4_2__
  static __m128i const _mask = { 0x200a0d09 };
  mask = _mask;
#else
  // to save on loads in l2, we pre-load these here, outside the loop.
  _space = _mm_set1_epi8(0x20);
  _nl = _mm_set1_epi8(0x0a);
  _cr = _mm_set1_epi8(0x0d);
  _tab = _mm_set1_epi8(0x09);
#endif
#endif
  for (size_t i=0; i<n; ) {
    for (; i<n && isspace(sv[i]); ++i) ;
    a=i;
#ifdef __SSE__
    b=i+l2(sv.data()+i);
    i=b;
#else
    for (; i<n && !isspace(sv[i]); ++i) ;
    b=i;
#endif
    if (a==b) break;
    string_view w(sv.substr(a,b-a));
    (*m)[w]++;
  }
}

const int threads=4;	// how many threads to launch

int main() {
  std::ios::sync_with_stdio(false);	// supposedly this makes cout faster

#if 0
  static char tmp[]="abc defhijk lmno p qrstu vw xyz\n";
  cout << l2(tmp) << "\n";
  cout << l2(tmp+1) << "\n";
  cout << l2(tmp+2) << "\n";
  cout << l2(tmp+3) << "\n";
  cout << l2(tmp+4) << "\n";
  return 0;
#endif

  // memory-map file from stdin
  struct stat ss;
  if (fstat(0,&ss)==-1) {
    cerr << "stdin not seekable!\n";
    return 1;
  }
  char* map=static_cast<char*>(mmap(nullptr,ss.st_size+16,PROT_READ|PROT_WRITE,MAP_PRIVATE,0,0));
  if (map==MAP_FAILED) {
    cerr << "could not mmap stdin!\n";
    return 1;
  }
  map[ss.st_size]=' ';

  try {		// shut up clang-tidy :-)

    // separate input into "threads" chunks, but make sure the
    // chunks don't split the input in the middle of a word
    size_t inc=ss.st_size/threads;	// approximate chunk size
    vector<size_t> ofs(threads);
    {
      // Adjust offsets in ofs[] from middle of word.
      // This code will fail on pathological inputs with ultra
      // long words (approaching chunk size)
      off_t n=inc;
      for (size_t i=0; i+1<threads; ++i) {
	for (; n<ss.st_size && !isspace(map[n]); ++n) ;	// skip to next word
	ofs[i]=n;
	n+=inc;
      }
    }

    // construct string_view from the adjusted offsets
    vector<string_view> slice;
    for (size_t i=0; i<threads; ++i) {
      if (i==0)
	slice.emplace_back(string_view(map, ofs[0]));
      else if (i+1<threads)
	slice.emplace_back(string_view(map+ofs[i-1], ofs[i]-ofs[i-1]));
      else
	slice.emplace_back(string_view(map+ofs[i-1], ss.st_size-ofs[i-1]));
    }

    // each thread will put its results into its own unordered_map
    // otherwise locking and contention will destroy the
    // performance gain from threading
    vector<robin_hood::unordered_map<string_view, int>> m(threads);
    vector<thread> t;

    // phase 1: tokenize
    for (size_t i=1; i<threads; ++i) {
      // launch threads
      t.emplace_back(thread(tokenize,slice[i],&(m[i])));
    }
    // do first chunk in this thread
    tokenize(slice[0],&(m[0]));

    for (size_t i=1; i<threads; ++i) {
      // wait until all threads are done
      t[i-1].join();
      // now add the counts from the hash table this thread filled to
      // the main thread's hash table. This used to be phase 2
      for (const auto& a : m[i]) {
	m[0][a.first] += a.second;
      }
    }

    // phase 3: sort
    vector<robin_hood::pair<string_view, int>> temp(m[0].begin(), m[0].end());
    sort(temp.begin(), temp.end(),
	[](auto const& a,auto const& b) { return b.second < a.second; } );

    // phase 4: output
    vector<string> output(4);
    {
      // Output is comparatively cheap, but we'll do it in multiple
      // threads anyway.
      size_t outslice = temp.size()/threads;
      for (size_t i=0; i<threads; ++i) {
	output[i].reserve(temp.size()/threads * 50);	// This is key. Reallocations kill perf.
	t[i]=thread([&temp,&output](size_t n,size_t l,size_t h) {
	  for (size_t i=l; i<h; ++i) {
	    output[n] += to_string(temp[i].second) + " ";
	    output[n] += temp[i].first;
	    output[n] += "\n";
	  }
	}, i, i*outslice, (i == threads-1 ? temp.size() : (i+1)*outslice) );
      }
      for (size_t i=0; i<threads; ++i) {
	t[i].join();
	write(1,output[i].data(),output[i].size());
      }
    }
#if 0
    // old, serial version
    for (const auto& a : temp)
      cout << a.second << " " << a.first << "\n";
#endif

  } catch (std::bad_alloc& e) {
    cerr << "out of memory\n";
  } catch (...) {
    cerr << "unexpected exception\n";
  }

  return 0;
}